Sorting Algorithms Cheat Sheet and Tutorial
Master the most commonly used sorting algorithms in computer science. This guide covers Bubble Sort, Quick Sort, Merge Sort, and Heap Sort, with step-by-step examples, time complexities, and space complexities for each.
1. Bubble Sort
Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted.
Time Complexity: O(n2)
Space Complexity: O(1)
Bubble Sort Example:
Initial list: [5, 3, 8, 4, 2]
Pass 1:
[3, 5, 8, 4, 2]
[3, 5, 8, 4, 2]
[3, 5, 4, 8, 2]
[3, 5, 4, 2, 8]
Pass 2:
[3, 5, 4, 2, 8]
[3, 4, 5, 2, 8]
[3, 4, 2, 5, 8]
Pass 3:
[3, 4, 2, 5, 8]
[3, 2, 4, 5, 8]
Pass 4:
[2, 3, 4, 5, 8]
Sorted list: [2, 3, 4, 5, 8]
2. Selection Sort
Selection Sort works by repeatedly finding the minimum element from the unsorted part of the list and swapping it with the first unsorted element. The process continues until the entire list is sorted.
Time Complexity: O(n2)
Space Complexity: O(1)
Selection Sort Example:
Initial list: [5, 3, 8, 4, 2]
Pass 1:
[2, 3, 8, 4, 5]
Pass 2:
[2, 3, 8, 4, 5]
Pass 3:
[2, 3, 4, 8, 5]
Pass 4:
[2, 3, 4, 5, 8]
Sorted list: [2, 3, 4, 5, 8]
3. Insertion Sort
Insertion Sort builds the final sorted list one item at a time. It works by repeatedly picking the next element and inserting it into its correct position in the already sorted part of the list.
Time Complexity: O(n2)
Space Complexity: O(1)
Insertion Sort Example:
Initial list: [5, 3, 8, 4, 2]
Pass 1:
[3, 5, 8, 4, 2]
Pass 2:
[3, 5, 8, 4, 2]
Pass 3:
[3, 4, 5, 8, 2]
Pass 4:
[2, 3, 4, 5, 8]
Sorted list: [2, 3, 4, 5, 8]
4. Merge Sort
Merge Sort is a divide-and-conquer algorithm that divides the list into two halves, recursively sorts them, and then merges the two sorted halves into one sorted list.
Time Complexity: O(n log n)
Space Complexity: O(n)
Merge Sort Example:
Initial list: [5, 3, 8, 4, 2]
Divide:
Left: [5, 3]
Right: [8, 4, 2]
Sort Left:
[3, 5]
Sort Right:
[4, 8]
[2, 4, 8]
Merge:
[2, 3, 4, 5, 8]
Sorted list: [2, 3, 4, 5, 8]
5. Quick Sort
Quick Sort is another divide-and-conquer algorithm. It works by selecting a pivot element, partitioning the list into two parts where one part contains elements smaller than the pivot and the other contains elements larger, and then recursively sorting the two parts.
Time Complexity: O(n log n) on average, O(n2) in the worst case
Space Complexity: O(log n) for the recursive stack
Quick Sort Example:
Initial list: [5, 3, 8, 4, 2]
Pivot: 5
Left: [3, 4, 2]
Right: [8]
Sort Left:
Pivot: 3
Left: [2]
Right: [4]
Merge Left:
[2, 3, 4]
Final merge:
[2, 3, 4, 5, 8]
Sorted list: [2, 3, 4, 5, 8]
6. Heap Sort
Heap Sort is a comparison-based sorting algorithm that builds a heap from the list and then repeatedly extracts the maximum element from the heap to build the sorted list.
Time Complexity: O(n log n)
Space Complexity: O(1)
Heap Sort Example:
Initial list: [5, 3, 8, 4, 2]
Build Heap:
[8, 5, 3, 4, 2]
Extract max (8):
[5, 4, 3, 2] and [8]
Extract max (5):
[4, 2, 3] and [5, 8]
Extract max (4):
[3, 2] and [4, 5, 8]
Extract max (3):
[2] and [3, 4, 5, 8]
Final sorted list: [2, 3, 4, 5, 8]
Conclusion
Each sorting algorithm has its strengths and weaknesses, and the best one to use often depends on the specific context or dataset you are working with. Understanding these algorithms is crucial for optimizing performance in various computational tasks.