Sorting Algorithms

Overview

Time complexity:

Algorithm	Time	Space
Bubble sort	O(n2)	O(1)
Insertion sort	O(n2)	O(1)
Selection sort	O(n2)	O(1)
Quicksort	O(nlog(n))	O(log(n))
Mergesort	O(nlog(n))	O(n)
Heapsort	O(nlog(n))	O(1)
Counting sort	O(n + k)	O(k)
Radix sort	O(nk)	O(n + k)
Binary Search	O(log(n))	/

---

Bubble Sort

This algorithm is commonly used to illustrate how a sorting algorithm works, it’s not recommended to actually use it because it’s a BruteForce algorithm, due to its nested for-loops.

BubbleSort repeatedly iterates through an array, at each index checking if arr[i] is greater or lesser than arr[i+1] and based on the condition it’ll swap the two elements’ places or not.

==// I advocate to call it “Swap sort”==

How it works

• Has a sorted part and an unsorted part.
• Each iteration:
  • Run ‘bubble’ across the unsorted part
  • The largest remaining bubbles to the end

Algorithm

// Sort array by bubble sort, input is unsorted array, and output is the same array rearranged
Algo BubbleSort(array A)
	// Array A of length n, A[0...n-1]
	for 0 <= i < n - 1:
		for 0 <= j < n - 2 - i:
			if A[j+1] < A[j]:
				swap A[j] and A[j+1]
				

Efficiency

Due to the nested for-loops, iterating over n elements in the worst-case scenario, this algorithm has a time complexity of $O(n^2)$.

Decrease and Conquer

Insertion Sort

Slightly better than Bubble Sort. It slowly builds the sorted array one step at a time (behind it) while iterating through the array, by taking the current element and inserting it to where it fits in the array while shifting all over elements. // I confuse this with Selection Sort all the time, dunno why...

How it works

1. Sort items A[0] and A[n-2]
2. Find the spot where A[n-1] (last item) fits.
3. Shift over all the other elements, and drop A[n-1] in that spot.

Algorithm

There’s the common iterative approach and a recursive approach. Iterative version:

Algorithm InsertionSort(A, n):
    for i = 1 to n - 1: // sequential selection from index 1
        key = A[i]
        j = i - 1
        while j ≥ 0 and A[j] > key: // comparison with sorted section
            A[j + 1] = A[j]
            j = j - 1
        A[j + 1] = key

And the implementation in Python:

def insertionSort(arr):
	for i in range(1, len(arr)):
		key = arr[i]
		j = i - 1
		while 0 <= j and key < arr[j]:
			arr[j + 1] = arr[j]
			j -= 1
		arr[J + 1] = key

Recursive version involving splitting the array

Algo InsertionSort(A,n)
	if n > 1
		 InsertionSort(A,n-1)
		 key = A[n-1]
		 i = n-2
			 while i ≥ 0 and A[i] > key
					 A[i+1] = A[i]
					 i = i - 1
			 A[i + 1] = key

Explanation:

1. The InsertionSort function recursively sorts the array A up to index $n-2$.
2. Then it inserts the element A[n-1] (the “key”) into the sorted portion of the array.
3. The while loop moves elements greater than key one position to the right.
4. The key is placed in its correct position.

Insertion sort and Selection sort Similarities

• “Sorted” and “unsorted” piles
• Each main iteration does two things:
  • Choose item from “unsorted
  • Place item in “sorted”
• Number of main iterations is $O(n)$
• $O(n^2)$ overall (worst case)

Insertion sort and Selection sort Differences

• Selection sort: each main iteration
• “Choose from unsorted part” is $O(n)$ (linear search)
• “Place into sorted part” is $O(1)$ (it goes at the end)
• Insertion sort: each main iteration
  • “Choose from unsorted part” is $O(1)$ (choose first item)
  • “Place into sorted part” is $O(1)$ (shift the other items)

Efficiency

The iterative version which is the one commonly spoken about does have an average time complexity of $O(n^2)$ but its best is $O(n)$

Not great for severely unsorted or large data sets.

Divide and Conquer

Merge Sort

A great and efficient algorithm that’s stable and based on comparisons. It’s also starring Recursion! It recursively divides the input array into two until it can compare the two halves and then start merging them together.

How it works

Algo Mergesort(Array A)
	if n > 1
		copy A[0...n/2 - 1] to B[0...n/2 - 1]
		copy A[0...n/2 - 1] to C[0...n/2 - 1]
		Mergesort(B[0...n/2 - 1])
		Mergesort(C[0...n/2 - 1])
		Merge(B,C,A)

The Merge function: Example: B = { 3 8 9 } and C = { 1 5 7 } → merge(B, C) = { 1 3 5 7 8 9 }

• Three different pointers (indices), one for each array and one for the sorted result. // Each set to 0, pointing to start of their respective arrays…
• Compare the smaller element at each index between the arrays, copy the smaller one into the result array.
• Then shift the index in the C array, but not in the B array.
• Then shift the index in the B array, but not in the C array // So alternate between which index is shifted.
• If one array ends, then copy the one that remains into the result.

// TODO: Try implementing in Python!

Heap Sort