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))	/

---

Brute Force

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 swa+p 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 element 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 - 1 - i:
			if A[j+1] < A[j]:
				swap A[j] and A[j+1]
				

After each pass, the next largest element is guaranteed to be in its correct position, at the end of the unsorted portion of the array…
So subtracting i from the limit of the inner-loop, ensures the inner-loop avoids re-checking the elements at the end of the array that are already sorted and in their final places…

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)$.
Making it unsuitable for real world applications, mostly just used for educational purposes.

Decrease and Conquer

Selection Sort

During each iteration, select the smallest element of the unsorted partition.
Then drop that element into its place in the sorted partition.

Algorithm

• start with min as first element, iterate until you find a smaller number
• If a smaller number is found:
  • set the new smallest
• swap the current element with the smallest

It’s still a bad algorithm, with a time complexity of $O(n^2)$

Python code:

def sel_sort(arr):
	for i in range(len(arr)): # 0 to n-1
		smallest = arr[i]
		for j in range(i+1, len(arr)): # i to n-1
			if arr[j] < smallest:
				smallest = arr[j]
		# swap them
		if(smallest != arr[i]):
			temp = arr[i]
			arr[i] = smallest
			smallest = temp

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.

It works by checking each element and comparing it to elements preceding it (on its left) and inserting in the correct position. Forming sorted and unsorted sections.

Algorithm

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

fn insertSort(array)
	for i = 1 to i < n - 1
		j = i
		while 0 < j AND array[j] < array[j-1]
			temp = array[j]
			array[j] = array[j-1]
			array[j-1] = temp
			j--
	

// This one's from Wikipedia, w but the next I found somewhere else...

Another implementation in Python:

def insertionSort(arr):
	for i in range(1, len(arr)):
		key = arr[i] # just temp hold of value
		j = i - 1 # j is the position before the current element
		while 0 <= j and key < arr[j]:
			arr[j + 1] = arr[j]
			j -= 1
		# drop the current element where it belongs
		arr[J + 1] = key

Note: the while loop shifts all the elements from 0 to i-1 and greater than current element

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

1. “Choose from unsorted part” is $O(n)$ (linear search)
2. “Place into sorted part” is $O(1)$ (it goes at the end)
   Insertion sort: each main iteration
   1. “Choose from unsorted part” is $O(1)$ (choose first item)
   2. “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