Module 3: Sorting (Elemental, Merge, Quick)¶

Note

This page only contains the notes for the module. It provides a big picture on the sorting algorithms.

Visualizations

Due to the complexity of the sorting algorithms. Visualizations may greatly enhance the learning process. Below are two useful websites providing visualizations of common algorithms and data structures.
- visualgo.net
- Data Structure Visualization
Categories
- Comparison based
  - Best algorithm complexity \(\Theta(n \log n)\)
  - The base type must be comparable (can use >, <, ==, etc.)
  - selection
  - insertion
  - bubble
  - shell
  - quick
  - merge
  - heap - to be covered in the next module
- Other (special requirements on the data type)
  - Bucket
  - Radix
  - Counting
Complexity
- simple \(\Theta(n^2)\): insert, selection, bubble
- fast \(\Theta(n \log n)\): quick, merge, heap
- linear
  - radix \(\Theta(nk) = \Theta(n)\)
  - bucket \(\Theta(n + k) = \Theta(n)\)
Storage Space
- in-place
  - iterative sorting algorithms \(\Theta(1)\)
  - recursive sorting algorithms \(\Theta(\log n)\) to \(\Theta(n)\) (due to the recursion stack)
- not-in-place (out-of-place)
  - Merge sort \(\Theta(n)\)

Comparison based sorting algorithms¶

In-place swap based sorting algorithms
- Selection sort
- Insertion sort
- Bubble sort
- Shell sort
Divide and conquer sorting algorithms
- Merge sort
- Quick sort
Hybrid sorting algorithms
- Divide and conquer to reduce the problem size
- in-place swap based sorting algorithms to sort when the problem size is small