Sorting Algorithms - Detailed Notes
Sorting Algorithms - Summary
What is a Sorting Algorithm?
A sorting algorithm is a method or process used to rearrange elements (typically numbers or strings) in a specific
order-ascending or descending.
Types of Sorting Algorithms:
1. Comparison-Based Sorting: Bubble, Selection, Insertion, Merge, Quick, Heap, Shell
2. Non-Comparison-Based Sorting: Counting, Radix, Bucket
Detailed Explanations:
1. Bubble Sort
Definition: Repeatedly compares adjacent elements and swaps them.
Advantages: Simple, good for small data.
Disadvantages: Slow for large data.
Time: Best O(n), Avg/Worst O(n^2); Space: O(1); Stable: Yes; In-place: Yes
2. Selection Sort
Definition: Selects min/max and swaps with start.
Advantages: Simple, no extra space.
Disadvantages: Inefficient for large data.
Time: O(n^2) all cases; Space: O(1); Stable: No; In-place: Yes
3. Insertion Sort
Definition: Inserts each item into its correct place in the sorted part.
Advantages: Efficient for small or nearly sorted data.
Disadvantages: Inefficient for large data.
Time: Best O(n), Avg/Worst O(n^2); Space: O(1); Stable: Yes; In-place: Yes
4. Merge Sort
Definition: Divide and merge sorted subarrays.
Advantages: Efficient, stable.
Disadvantages: Requires extra space.
Time: All O(n log n); Space: O(n); Stable: Yes; In-place: No
5. Quick Sort
Definition: Partition using a pivot and recursively sort.
Advantages: Fast in practice, in-place.
Disadvantages: Not stable, worst-case O(n^2).
Time: Best/Avg O(n log n), Worst O(n^2); Space: O(log n); Stable: No; In-place: Yes
6. Heap Sort
Definition: Build a heap and sort.
Advantages: Good worst-case performance.
Disadvantages: Not stable.
Time: All O(n log n); Space: O(1); Stable: No; In-place: Yes
Sorting Algorithms - Detailed Notes
7. Shell Sort
Definition: Generalized insertion sort with gaps.
Advantages: Better than insertion for medium size.
Disadvantages: Depends on gap sequence.
Time: Best O(n log n), Avg O(n^1.5), Worst O(n^2); Space: O(1); Stable: No; In-place: Yes
8. Counting Sort
Definition: Counts occurrences and places items.
Advantages: Fast for small ranges.
Disadvantages: Not for large ranges.
Time: O(n + k); Space: O(k); Stable: Yes; In-place: No
9. Radix Sort
Definition: Sort by digits using a stable sort.
Advantages: Linear time for fixed-size integers.
Disadvantages: Needs stable sort, not for floats.
Time: O(nk); Space: O(n + k); Stable: Yes; In-place: No
10. Bucket Sort
Definition: Divide into buckets, sort individually.
Advantages: Fast for uniformly distributed data.
Disadvantages: Performance depends on data distribution.
Time: Best/Avg O(n + k), Worst O(n^2); Space: O(n + k); Stable: Yes; In-place: No
