1. Bubble Sort
Description:
Bubble Sort is a simple comparison-based algorithm where adjacent elements are compared and swapped if they are in the wrong order. This process repeats until the entire array is sorted.
Steps:
Given: [5, 3, 8, 4, 2]
- Compare 5 and 3, swap: [3, 5, 8, 4, 2]
- Compare 5 and 8, no swap: [3, 5, 8, 4, 2]
- Compare 8 and 4, swap: [3, 5, 4, 8, 2]
- Compare 8 and 2, swap: [3, 5, 4, 2, 8]
Repeat until the list is sorted: [2, 3, 4, 5, 8]
Time Complexity:
- Best Case: O(n) (already sorted)
- Average Case: O(n^2)
- Worst Case: O(n^2)
Space Complexity:
- O(1) (in-place sorting)
2. Selection Sort
Description:
Selection Sort selects the smallest element from an unsorted portion and swaps it with the leftmost unsorted element.
Steps:
Given: [5, 3, 8, 4, 2]
- Find the smallest element (2), swap with 5: [2, 3, 8, 4, 5]
- Find the smallest element (3), no swap: [2, 3, 8, 4, 5]
- Find the smallest element (4), swap with 8: [2, 3, 4, 8, 5]
- Find the smallest element (5), swap with 8: [2, 3, 4, 5, 8]
Time Complexity:
- Best Case: O(n^2)
- Average Case: O(n^2)
- Worst Case: O(n^2)
Space Complexity:
- O(1)
3. Insertion Sort
Description:
Insertion Sort builds the final sorted array one item at a time by comparing and inserting elements in the correct position.
Steps:
Given: [5, 3, 8, 4, 2]
- Compare 3 with 5, insert: [3, 5, 8, 4, 2]
- Compare 8, no move needed: [3, 5, 8, 4, 2]
- Compare 4, insert before 8: [3, 4, 5, 8, 2]
- Compare 2, insert at the beginning: [2, 3, 4, 5, 8]
Time Complexity:
- Best Case: O(n)
- Average Case: O(n^2)
- Worst Case: O(n^2)
Space Complexity:
- O(1)
4. Merge Sort
Description:
Merge Sort is a divide-and-conquer algorithm that splits the array into halves, sorts each half, and merges them back together.
Steps:
Given: [5, 3, 8, 4, 2]
- Split: [5, 3] and [8, 4, 2]
- Split further: [5], [3], [8], [4, 2]
- Merge: [3, 5], [2, 4, 8]
- Merge final: [2, 3, 4, 5, 8]
Time Complexity:
- Best Case: O(n log n)
- Average Case: O(n log n)
- Worst Case: O(n log n)
Space Complexity:
- O(n) (due to extra space for merging)
5. Quick Sort
Description:
Quick Sort is a divide-and-conquer algorithm that selects a “pivot” and partitions the array around the pivot.
Steps:
Given: [5, 3, 8, 4, 2]
- Choose pivot (2), partition: [2] + [5, 3, 8, 4]
- Choose pivot (4), partition: [3] + [4] + [5, 8]
- Final: [2, 3, 4, 5, 8]
Time Complexity:
- Best Case: O(n log n)
- Average Case: O(n log n)
- Worst Case: O(n^2) (when pivot is the smallest or largest element)
Space Complexity:
- O(log n) (for recursion)
6. Heap Sort
Description:
Heap Sort uses a binary heap to repeatedly extract the largest (or smallest) element and rebuild the heap.
Steps:
Given: [5, 3, 8, 4, 2]
- Build heap: [8, 5, 3, 4, 2]
- Extract max: [8], reheapify: [5, 4, 3, 2]
- Continue until: [2, 3, 4, 5, 8]
Time Complexity:
- Best Case: O(n log n)
- Average Case: O(n log n)
- Worst Case: O(n log n)
Space Complexity:
- O(1)
Comparison of Sorting Algorithms
| Algorithm | Best Case | Average Case | Worst Case | Space Complexity | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) | O(1) | No |
| Insertion Sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) | O(n log n) | O(n^2) | O(log n) | No |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
Which Sorting Algorithm is Better?
- Quick Sort is generally the fastest for large datasets but is unstable.
- Merge Sort is best for consistent performance and stability.
- Heap Sort is useful for in-place sorting with good performance.
- Insertion Sort is effective for small datasets or nearly sorted data.
- Bubble Sort is useful for educational purposes but inefficient otherwise.
- Selection Sort is simple but slow due to its O(n^2) complexity.