Sorting Algorithms
1. Selection Sort
- Idea: Repeatedly find the minimum element and move it to the beginning.
- Time Complexity: $O(n^2)$
- In-place: Yes (No additional space required.)
- Stable: No (Does not maintain the relative order of equal elements in the input.)
flowchart TD
S0["Unsorted: [29, 10, 14, 37, 13]"]
S1["Find Min (10) → Swap with 29"]
S2["[10, 29, 14, 37, 13]"]
S3["Find Min (13) from index 1 → Swap with 29"]
S4["[10, 13, 14, 37, 29]"]
S5["Find Min (14) from index 2 → Already in place"]
S6["[10, 13, 14, 37, 29]"]
S7["Find Min (29) from index 3 → Swap with 37"]
S8["Sorted: [10, 13, 14, 29, 37]"]
S0 --> S1 --> S2 --> S3 --> S4 --> S5 --> S6 --> S7 --> S8
2. Bubble Sort
- Idea: Repeatedly swap adjacent elements if they are in the wrong order.
- Time Complexity: $O(n^2)$
- In-place: Yes
- Stable: Yes
flowchart TD
B0["Unsorted: [5, 3, 8, 4, 2]"]
B1["Pass 1: Compare and swap → [3, 5, 4, 2, 8]"]
B2["Pass 2: [3, 4, 2, 5, 8]"]
B3["Pass 3: [3, 2, 4, 5, 8]"]
B4["Pass 4: [2, 3, 4, 5, 8]"]
B0 --> B1 --> B2 --> B3 --> B4
3. Insertion Sort
- Idea: Build the sorted array one item at a time by inserting elements into their correct position.
- Time Complexity: $O(n^2)$
- In-place: Yes
- Stable: Yes
flowchart TD
I0["Start: [7, 2, 4, 10, 1]"]
I1["Insert 2 before 7 → [2, 7, 4, 10, 1]"]
I2["Insert 4 before 7 → [2, 4, 7, 10, 1]"]
I3["10 in correct place → [2, 4, 7, 10, 1]"]
I4["Insert 1 at start → [1, 2, 4, 7, 10]"]
I0 --> I1 --> I2 --> I3 --> I4
4. Merge Sort
- Idea: Divide the array into halves, recursively sort them, and merge the sorted halves.
- Time Complexity: $O(n \log n)$
- In-place: No
- Stable: Yes
graph TD
A["[38, 27, 43, 3, 9, 82, 10]"]
B1["[38, 27, 43]"]
B2["[3, 9, 82, 10]"]
C1["[38]"]
C2["[27, 43]"]
C3["[3, 9]"]
C4["[82, 10]"]
D1["[27]"]
D2["[43]"]
D3["[3]"]
D4["[9]"]
D5["[82]"]
D6["[10]"]
M1["[27, 43] → [27, 43]"]
M2["[38] + [27, 43] → [27, 38, 43]"]
M3["[3, 9] → [3, 9]"]
M4["[82, 10] → [10, 82]"]
M5["[3, 9] + [10, 82] → [3, 9, 10, 82]"]
M6["[27, 38, 43] + [3, 9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]"]
A --> B1
A --> B2
B1 --> C1
B1 --> C2
C2 --> D1
C2 --> D2
B2 --> C3
B2 --> C4
C3 --> D3
C3 --> D4
C4 --> D5
C4 --> D6
D1 --> M1
D2 --> M1
C1 --> M2
M1 --> M2
D3 --> M3
D4 --> M3
D5 --> M4
D6 --> M4
M3 --> M5
M4 --> M5
M2 --> M6
M5 --> M6
5. Quick Sort
- Idea: Pick a pivot, partition the array such that left < pivot < right, and sort subarrays recursively.
-
Time Complexity:
- Best & Avg: $O(n \log n)$
- Worst: $O(n^2)$
- In-place: Yes
- Stable: No
graph TD
A["[9, 4, 7, 3, 10, 5]"]
B["Pivot: 5 → Partition → [4, 3] + [5] + [9, 7, 10]"]
L1["[4, 3]"]
L2["[5]"]
R1["[9, 7, 10]"]
LL1["Pivot: 4 → Partition → [3] + [4] + []"]
RL1["Pivot: 9 → Partition → [7] + [9] + [10]"]
L3["[3]"]
L4["[4]"]
L5["[]"]
R3["[7]"]
R4["[9]"]
R5["[10]"]
S1["[3, 4]"]
S2["[7, 9, 10]"]
S3["[3, 4, 5, 7, 9, 10]"]
A --> B
B --> L1
B --> L2
B --> R1
L1 --> LL1
LL1 --> L3
LL1 --> L4
LL1 --> L5
R1 --> RL1
RL1 --> R3
RL1 --> R4
RL1 --> R5
L3 --> S1
L4 --> S1
R3 --> S2
R4 --> S2
R5 --> S2
S1 --> S3
L2 --> S3
S2 --> S3