Sorting

Sorting

1. Insertion Sorts

   • Straight
     • Like sorting a deck of cards in your hand Average = O(n^2)

2. Exchange sorts

   • Bubble
     • Smallest item "bubbles up" to top of list Average = O(n^2)
   • Quicksort
     • Recursive Select pivot that divides elements into 2 sets (smaller or larger than p). Reinsert p into correct position. Call method again. Average = O(n log(n))

3. Selection Sorts

   • Straight
     • Find largest (or smallest) and swap with the beginning or end of a list O(n^2)

4. Merge Sorts

   • Recursive 2 sorted sequences can be merged into one larger sorted sequence O(n log(n))

5. Distribution Sorts

   • Bucket
     • O(n) Main idea: element to be sorted come from a relatively small, finite universe
   • Radix
     • Aka least-significant-digit-first radix sort Extention of bucket sort with larger universes

Images and files in the map