Intro to Sorting

Nov. 18, 2020 pexels-pixabay-35888.jpg Vuong Huynh

Bubble Sort

Bubble Sort: comparing elements side by side and switching them if necessary.

While sorting, the biggest (or smallest) element will be BUBBLED UP to the top.

For example, we have an array [8, 3, 1, 7, 0] and want to sort them from smallest to biggest. We need to iterate through the array (at least one time)

First iteration:

  1. We compare the first and second elements: 8 and 3. Because 8 > 3 we need to switch them. The array becomes [3, 8, 1, 7, 0]
  2. Continuing to the second and third elements: 8 and 1, 8 > 1, switch them. The array now is [3, 1, 8, 7, 0]
  3. Next are the third and fourth elements: 8 and 7, 8 > 7, switch them. We have [3, 1, 7, 8, 0]
  4. Finally (actually not final yet), the fourth and last elements, 8 and 0, switch. Now the array is [3, 1, 7, 0, 8]. Not really what we want.

Second iteration: we do the same thing as the first iteration with a sorted array [3, 1, 7, 0, 8]:

  1. Compare first and second elements and switch, the array becomes [1, 3, 7, 0, 8]
  2. Compare second and third elements. No need to switch
  3. Compare the third and fourth elements. Switch and the array become [1, 3,0, 7, 8]
  4. Compare the fourth and last elements. No need to switch.

Third iteration: repeat the boring steps, we will have the array [1, 0, 3, 7, 8]. Still not look good.

Fourth iteration: go again and finally; the array is sorted as we want [0, 1, 3, 7, 8]


The efficiency of Bubble Sort

In every iteration above, we had to do 4 steps for 5 elements, which is n - 1. And we did 4 iterations in total.

Let's make a table and see more closely

Iteration # 1 2 3 4
# of comparisons n - 1 n - 1 n - 1 n - 1

So we have (n - 1) iterations and (n - 1) comparisons. Which give us (n - 1)(n - 1) = n2 - 2n + 1

With the approximative approach, we will have the efficiency of Bubble Sort:

O(n2) in time

O(n) in space

In fact, we could save some time of the algorithm by not checking the last element (and last element += 1) after every iteration. However, this does not help much.

Notes:

  • Worst Case = O(n2)
  • Average Case = O(n2)
  • Best Case = O(n) - where the array is already sorted and we only have to iterate through the array only once.

See more in Bubble Sort - Wikipedia

Merge Sort

Merge Sort: split a huge array down as much as possible and build it back up while comparing and sorting at each step along the way.

The idea of breaking for sorting and building again is called Divide and Conquer.

Suppose we have an array [8, 3, 1, 7, 0, 10, 2]

We firstly break it up into smaller arrays [8], [3], [1], [7], [0], [10], and [2].

We also need placeholders for the first merge [ ], [ , ], [ , ], and [ , ]

First iteration (3 comparison steps): we compare (switch if needed) two arrays and put them into the placeholders

  1. [8] - no need to compare
  2. [3], [1] - switch to [1, 3]
  3. [7], [0] - switch to [0, 7]
  4. [10], [2] - switch to [2, 10]

Second iteration (5 comparison steps): we will do the same with larger size of place holder [ , , ] and [ , , , ]

Compare and merge: [8] and [1, 3]

  1. Compare 8 and 1, 8 > 1, put 1 into the placeholder [1, , ]
  2. Compare 8 and 3, 8 > 3, put 3 then 8 to the placeholder [1, 3, 8]

Compare and merge: [0, 7] and [2, 10]

  1. Compare 0 and 2, 0 < 2, put 0 into placeholder [0, , , ]
  2. Compare 7 and 2, 2 < 7, put 2 into placeholder [0, 2, , ]
  3. Compare 7 and 10, 7 < 10, put 7 and then 10 into placeholder [0, 2, 7, 10]

Third iteration (6 comparison steps): we now compare two array [1, 3, 8] and [0, 2, 7, 10] then put them into the placeholder with size 7 [ , , , , , , ]

  1. Compare 1 and 0, 0 < 1, put 0 into the placeholder [ 0, , , , , , ]
  2. Compare 1 and 2, 1 < 2, put 1 into the placeholder [ 0, 1, , , , , ]
  3. Compare 2 and 3, 2 < 3, put 2 into the placeholder [ 0, 1, 2, , , , ]
  4. Compare 3 and 7, 3 < 7, put 3 into the placeholder [ 0, 1, 2, 3, , , ]
  5. Compare 8 and 7, 7 < 8, put 7 into the placeholder [ 0, 1, 2, 3, 7, , ]
  6. Compare 8 and 10, 8 < 10, put 8 then 10 into the placeholder [ 0, 1, 2, 3, 7, 8, 10]


The efficiency of Merge Sort

We have 3 iterations and 14 steps of comparison for a size 7 array from the above example.

With an array size of n, we need 2n steps of comparison, or approximately O(n)

We can make a table as before:

Array size 1 2 3 4 5 6 7 8 9
# Iterations 0 1 2 2 3 3 3 3 4

With an array size of 1, we need 0 iteration

With an array size of 2, we need 1 iteration

Array size 3 or 4, we need 2 iterations

Array size 5, 6, 7, or 8, we need 3 iterations (as the example above)

Array size 9 to 16, we need 4 iterations, and so on.

We can see after every power of 2, we will need to increase the number of iteration by 1. Similar to the binary search, we have the time efficiency of log(n).

Combining the number of iterations and comparison steps, we have the time efficiency of Merge Sort:

O(nlog(n))

Another example of Merge Sort:

[21, 4, 1, 3, 9, 20, 25] (Original Array)
[21, 1, 4, 3, 9, 20, 25] (1 - iteration)
[1, 4, 21, 3, 9, 20, 25] (2 - iterations)
[1, 3, 4, 9, 20, 21, 25] (3 - iterations)

Quick Sort

In many cases, Quick Sort is one of the most efficient sorting algorithms.

The Quick Sort needs an element as a pivot, divide and conquer, and then sort the array in-place but unstable.

For the pivot, we can pick the first element, last element, random element, or the median element.

In this example, we will use the last element as our pivot.

To start Quick Sort, we need to initially pick the last element as a pivot. Comparing the pivot with the first element, if the value of that element is larger than the value of the pivot, we swap their positions.

However, we are doing an in-place sort, we will need to move the element in front of the pivot to make room instead of using a placeholder.

Let's go with the example of the array: [ 8, 3, 1, 7, 0, 10, 2]

  • First, we pick 2 as the pivot. Compare 2 to 8 - the first element, 8 > 2, we move 8 to the position of 2, we also need to move 2 to the position in front of it where 10 is. And we move 10 to the position of 8. The new array become [10, 3, 1, 7, 0, 2, 8]
  • Continue with our pivot 2, comparing 2 to 10, 10 > 2, move 10 to the position of 2, move 2 to the position of 0 - the front position of the pivot, and move 0 to the position of 10. We have [ 0, 3, 1, 7, 2, 10, 8]
  • Compare 2 to 0 - the first element, 2 > 0, check the next element 3, 3 > 2, move 3 to the position of 2, move 2 to the front position 7, move 7 to the position of 3. The new array [ 0, 7, 1, 2, 3, 10, 8]
  • Compare 2 to 7, move 7 to the position of 2, move 2 to the front element - 1, and move 1 to the position of 7. We have [ 0, 1, 2, 7, 3, 10, 8]
  • 2 is in the right position since it is bigger than 0 and 1.
  • We now do the same process with the element smaller than the pivot and then bigger than the pivot. We start checking 0 and 1, they are in a good place. So we check the bigger elements than 2.
  • We need to pick a new pivot - 8 as a convention. Compare 8 with 0, 1, 2, 7, 3, 10. 10 > 8, we swap the position of 10 and 8. We now have [ 0, 1, 2, 7 , 3, 8, 10]
  • 8 or 10 are in a good position because it is bigger than any element in front of it. We continue checking the elements smaller than 8.
  • Now we only have 7 and 3. Pick 3 as the new pivot, compare 3 to 7, 7 > 3, swap them. Now we have the whole array sorted [ 0, 1, 2, 3, 7, 8 10]


The efficiency of Quick Sort

In the worst case, time efficiency is:

O(n2)


Implementation

In the implementation, we will use the first element as our pivot.

def quick_sort(arr):
    
    arr_len = len(arr)

    if arr_len <= 1:
        return arr

    pivot = 0

    for i in range(1, arr_len):
        if arr[i] <= arr[0]:
            pivot += 1
            arr[i], arr[pivot] = arr[pivot], arr[i]

    arr[0], arr[pivot] = arr[pivot], arr[0]

    smaller = quick_sort(arr[0:pivot])
    larger = quick_sort(arr[pivot + 1:arr_len])

    arr = smaller + [arr[pivot]] + larger

    return arr

array = [8, 3, 1, 7, 0, 10, 2]

print("Original Array: ",array)
print("Sorted Array: ",quick_sort(array))

More references on Quick Sort:

Quick Sort - GeeksforGeeks

VisuAlgo - Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix)

Quicksort in Python By Olivera Popović