Sorting Algorithms

Properties

• In Place: Uses a minimal, constant amount of extra memory (not dependent on N)
  • Yes: Bubble, Selection, Insertion, Quick
  • No: Merge, Counting, Radix
• Stable: Two equal elements in the input array maintain their order in the output
  • Yes: Bubble, Insertion, Merge, Counting (depends), Radix
  • No: Selection, Quick (unless using special stable partition)

Bubble Sort

1. Compare adjacent elements, swap them if not in order, repeat until reaching the end of the array
2. Now, the largest element will be in the at position n-1
3. Repeat step 1, but stop at n-1, n-2 etc. until we stop at the first element
4. Optionally, can terminate early when we go through the whole array without performing any swaps

function bubbleSort(arr) { 
  const n = arr.length;
  for (let r = n - 1; r > 0; r--) // Repeat n-1 times 
    for (let i = 0; i < r; i++) // The 'unsorted region' 
		if (arr[i] > arr[i + 1]) swap(arr, i, i+1);
}

• Iterations: $(N-1)+(N-2)+...+1=N\times (N-1)/2$
• Time: $c\times N\times \frac{N-1}{2}=O(N^2)$

Selection Sort

1. Start with i=0
2. Go through the array from i to last element to find index of the smallest element
3. Swap the smallest element with i
4. i++, then repeat steps 2-3, until i = n-2

function selectionSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minI = i;
    for (let j = i + 1; j < n; j++)
      if (arr[j] < arr[minI]) minI = j;
    swap(arr, i, minI)
  }
}

• Iterations: Similar to bubble sort
• Time: Similar to bubble sort $O(N^2)$

Insertion Sort

1. Start with the element i = 1
2. Go through the array backwards starting from i. If the current element is greater than the ith element, move it to the right one place (i.e. shift all elements greater than ith element one space to the right)
3. When we find an element smaller than ith element, set the element infront of it to ith element (i.e. insert ith element at the correct place)
4. i++, and repeat steps 2-3 until i = n-1

function insertionSort(arr) {
  const n = arr.length;
  for (let i = 1; i < n; i++) {
    const x = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > x) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = x;
  }
  return A;
}

• Time
  • Best case: Already sorted, so arr[j]>x is always false, then $O(N)$
  • Worst case: Sorted in reverse, so insertion is always at the front of the array, then $O(N^2)$

Merge Sort

1. Divide the array into two halves
2. Merge Sort each of the halves (base case is when there is a single element in the array, in which case it is already sorted)
3. Merge the two sorted halves into a sorted array

function mergeSort(arr, low, high)  
  // array to be sorted is arr[low..high]  
  if (low < high) // base case: low >= high means there are <1 items   
    const mid = Math.floor((low+high) / 2)  
    mergeSort(arr, low, mid)
    mergeSort(arr, mid+1, high)
    merge(arr, low, mid, high)

• Time:
  • Level 1: 2^0=1 calls to merge() with N/2^1 items each, O(2^0 x 2 x N/2^1) = O(N)
  • Level 2: 2^1=2 calls to merge() with N/2^2 items each, O(2^1 x 2 x N/2^2) = O(N)
  • Level 3: 2^2=4 calls to merge() with N/2^3 items each, O(2^2 x 2 x N/2^3) = O(N)
  • Overall, there are $\log n$ levels, each with $O(N)$ work, so overall time is $O(N\log N)$
  • Merge sort is ALWAYS $O(N\log N)$
• Space: Requires additional $O(N)$ space
• Notes
  • It is a stable sorting algorithm
  • Not in-place

Quicksort

1. Select a pivot and partition the array, items smaller than pivot on left, greater than pivot on right. Items equal to pivot have 50% chance of ending up on either side
2. Move the pivot to the space between the two partitions (this is the position of the pivot value in the final array) → (2, 5, 3, …), 6, (7, 9, 8, …)
3. Repeat steps 1-2 on the two partitions (excluding the pivot)

function partition(arr, low, high) {
  const pivot = arr[low];
  let bound = low + 1;
  for (let curr = low + 1; curr <= high; curr++) {
    if (arr[curr] < pivot || (Math.random() < 0.5 && arr[curr] == pivot)) {
      swap(curr, bound);
      bound++;
    }
  }
  swap(arr, low, bound - 1);
  return bound - 1; // return mid
}
 
function qs(arr, low, high) {
  if (low < high) {
    const mid = partition(arr, low, high);
    qs(arr, low, mid - 1);
    qs(arr, mid + 1, high);
  }
}
 

• Time
  • Pivot always chosen as first element
    • Worst case: array already sorted, each recursive call has only one element in the left array, so we recurse n times, and it is $O(n^2)$
    • Best case: partition always splits array into equal halves, in which case it is $O(n\log n)$
  • Random element chosen as pivot
    • Average case: $O(n\log n)$
  • Randomly assigning elements equal to the pivot to one partition
    • Avoids $O(n^2)$ time complexity when sorting arrays with many duplicate values, makes it closer to $O(n\log n)$ on average

Counting Sort

Can be used when the items to be sorted are in a small range

1. Create an array with length k, where k is the greatest value to be sorted
2. Go through the items to be sorted (x), and for each, arr[x]++
3. Go through the count array and create a new array with arr[i] elements with value i, in order they appear in arr

• Time: Count frequencies: O(N), create output: O(N+k), where k is the greatest value to be sorted

Radix Sort

For integers with large range but few digits

1. Take integers elements as a string of digits, pad elements with less digits with leading zeros so that all elements have the same number of digits
2. Based on the least significant (rightmost) digit, put each element into a queue, (one for each digit), similar to counting sort
3. Concatenate the groups to form a list sorted by least significant digit
4. Repeat 2-3 for all digits, starting with second least significant

• Time: $O(w\times (N+k)$ , where $w$ is length of the elements, $N$ is number of elements, and $k$ is the number of digits (for base 10, k=10)

Time Complexity

Input type → ↓ Algorithm	Random	Sorted N-d	Sorted N-i	Nearly Sorted N-d	Nearly Sorted N-i	Many Duplicates
(Opt) Bubble Sort	$N^2$	$N$	$N^2$	$N$	$N^2$	$N^2$
(Min) Selection Sort	$N^2$	$N^2$	$N^2$	$N^2$	$N^2$	$N^2$
Insertion Sort	$N^2$	$N$	$N^2$	$N$	$N^2$	$N^2$
Merge Sort	$N\log N$	$N\log N$	$N\log N$	$N\log N$	$N\log N$	$N\log N$
Quick Sort	$N\log N$	$N^2$	$N^2$	$N^2$	$N^2$	$N^2$
(Rand) Quick Sort	$N\log N$	$N\log N$	$N\log N$	$N\log N$	$N\log N$	$N\log N$
Counting Sort	$N$	$N$	$N$	$N$	$N$	$N$