4. Introduction to Sorting
4.1 What is Sorting?
Sorting is the process of arranging elements in a specific order (ascending or descending).
Why Sort?
- Faster Searching: Enables binary search
- Data Organization: Makes data easier to understand
- Algorithm Requirements: Many algorithms require sorted input
- Data Presentation: Better user experience
- Finding Duplicates: Easier with sorted data
Real-World Examples:
- Sorting contacts alphabetically
- Arranging files by date
- Organizing products by price
- Ranking search results
- Leaderboards in games
4.2 Sorting Algorithm Categories
1. By Complexity:
- Simple: Bubble, Selection, Insertion Sort - O(n²)
- Efficient: Merge, Quick, Heap Sort - O(n log n)
- Special: Counting, Radix, Bucket Sort - O(n)
2. By Method:
- Comparison-based: Compare elements to sort
- Non-comparison: Use element properties
3. By Stability:
- Stable: Preserves relative order of equal elements
- Unstable: May change relative order
4. By Memory:
- In-place: O(1) extra space
- Out-of-place: O(n) extra space
4.3 Sorting Algorithm Comparison Table
| Algorithm | Best | Average | Worst | Space | Stable | Method |
|---|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Exchange |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No | Selection |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Insertion |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | Divide & Conquer |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Divide & Conquer |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Selection |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes | Non-comparison |
| Radix Sort | O(d(n+k)) | O(d(n+k)) | O(d(n+k)) | O(n+k) | Yes | Non-comparison |