Sorting

Sorting is the act of re/ordering an input based off of some criteria.

A sort is stable if the algorithm can always provide elements deemed equal in the same position.

To-do

  • Above:
    • partial order
    • total-ordering
    • etc.
  • Sorting
    • Graph: Kahn’s Algorithm for topological sorting
    • Intro sort
    • Insertion sort
    • Heap Sort

Heap Sort

#sort#heap-sort

Merge Sort

#sort#divide-and-conquer#merge-sort

An efficient, general purpose, comparison-based Divide and Conquer sorting algorithm. Algorithm Divide the unsorted list into $n$ sublists, each containing one element. A list of one element is considered sorted. Repeatedly merge sublists to produce new sorted sublists, until only one list remains. Top-down implementation This implementation is $O(nlogn)$ as every iteration on $n$ causes work on half as much $n$.

Quick Sort

#sort#divide-and-conquer#quick-sort

An efficient, general purpose, comparison-based (total-order) Divide and Conquer sorting algorithm. Slightly faster than Merge Sort. Quick-sort works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays, based on their value compared to the pivot. This creates two sub-arrays where all elements in the first, are is less than any element in the second. The sub-arrays are then sorted recursively (can be done in-place).