Intro to Sorting Algorithms

We use sorting algorithms to keep an array in order. Here is a list of common sorting algorithms. Beware: the first three are highly inefficient! (See Time Complexity )

Bubble Sort: $O(n^2)$#

  • Set the first element as the current element.
  • swap(current, next) if current > next, essentially moving it down the list
  • Repeat last step.
    • if current < next: set next as the current element
    • if current = end of list: set the first element as the current element
  • The array is sorted when no swaps occur in a single pass (from first to last).
  • Intuition: “bubble” larger elements up to the end of the array.

Selection Sort: $O(n^2)$#

  • Split array into [ sorted | unsorted ] (initially sorted has 0 elements).
    • Note: they are still in the same array; use a counter to keep track of the split
  • Repeat until there is 0 element in unsorted.
    • Find the lowest value in array.
    • Swap it with the first element of the unsorted portion.
    • Extend the sorted array by one element (counter++) to include the new lowest value.
      • The new lowest value is always larger than all elements in sorted.
  • Repeat (search, swap, extend).
  • The sorted array will contain a list of “minimum values” in increasing order.

Insertion Sort: $O(n^2)$#

  • Split array into [ sorted | unsorted ] (initially sorted has 0 elements).
  • Repeat.
    • Get the first element from the unsorted array.
    • Iterate the sorted array backwards.
      • if current <= unsorted element: insert unsorted after current; break out of loop.
  • Sorting is complete when unsorted has 0 elements.

Merge Sort: $O(n\log{n})$#

  • Merge sort is a divide-and-conquer algorithm
    • Divide the task (sorting) into smaller tasks recursively (i.e. until they are indivisible / as easy as possible).
    • Solve the easy task.
    • Combine solutions to solve the larger / harder tasks.
  • First treat each element as one-element subarrays. These arrays are sorted.
  • Combine one-element subarrays (always two at a time) into two-element subarrays. This is trivial; just place the smaller element first.
  • To combine arrays with length $l \ge 4$ (all subarray lengths are powers of two):
    • Iterate both arrays at the same time. Use two separate counters (i, j) to keep track.
    • Keep a third counter (k). You will use this counter to index and replace the original array element’s value (You are doing the sorting in place to save space; You will at most need as much free space as two times the size of the original array).
    • if first[i] < second[j], then array[k] = first[i], i++, k++ (++ increments a variable by one)
    • else, array[k] = second[j], j++, k++
    • Repeat until one of the arrays run out of values. Copy the rest of the other array back into the original (they are already sorted as a subproblem)
  • The array is sorted when all the subarrays (subproblems) have been sorted and combined.

More sorting algorithms#



Created By: WHS Comp Sci Club Officers

CC-BY-NC-SA 4.0 | WHS CSC 2021