Flatiron Phase1

In this blog, I will take a look at 2 commonly used algorithms and address the benefits and caveats for each algorithm:

• Bubble Sort

• Quick Sort

Bubble sort is a simple sorting algorithm.
It iterates through the list and find two item i and i + 1, if list[i] is larger than list[i + 1], swap the two item.
The worst complexity it can reach is O(n^2).
It's easier to understand but not useful for large amount of data. One possible application is to list mostly sorted.

Below is what I wrote based on my understanding
while sorted == False:
sorted = True
for i in range(len(list) - 1):
if list[i] > list[i + 1]:
list[i], list[i + 1] = list[i + 1], list[i]
sorted = False
print(list)

Quick Sort has an average complexity of O(nlog(n)) but worst case is O(n^2). It's one of the most often used divide and conquer algorithm. The pseudo code is below

1. Select a pivot for the array, I will use rightmost element in this case
2. Partitioning: this is an important step, elements smaller than pivot at partitioned to the left, and elements greater than pivot are partitioned to the right. 3.Once all elements are iterated, pivot will be switched with the last item larger than pivot. So that on the left, all elements are smaller than pivot. On the right, all elements are larger than pivot. Neither side needs to be in order.
3. After partitioning, the process will be run again for the left and right partition of the array.

Quick sort is efficient and doesn't require extra memory to do the recursion (like merge sort)