Sorting Algorithms

Bubble Sort

• Compare adjacent elements and swap if needed

• Best Case O(n) sorted data

• Worst Case O(n²) unsorted data

• Avg O(n²)

• In place

• Stable

Bucket Sort

• Put elements into multiple buckets

• Sort Buckets individually and then merge back together

• best O(n + k)

• worst O(n²)

Counting Sort

• Count how many times each number occurs using array

• list numbers in another array based on occurences

• Stable

• O(n + k) time

Insertion Sort

• Marks first sorted element

• works through list putting elements in correct place relative to sorted list

• Best Case O(n) sorted data

• Worst Case O(n²) unsorted data

• Stable

• In place

Merge Sort

• Break array into smaller and smaller list

• sort small lists

• merge back together

• consistent O(nlogn)

• not in place

• stable

Quick Sort

• choose a pivot

• have two pointers at opposite ends of array

• move right pointer until find element less than pivot

• move left pointer until find element greater than pivot

• swap values at pivots

• repeat until pointers cross

• O(nlogn) best

• O(n²) worst

Radix Sort

• sort numbers digit by digit from LSD to MSD

• O(nk) time

• Good for large numbers with fixed size

• strings

Selection Sort

• find min element

• swap with next unsorted element

• O(n²)