What is Sorting ?
Organising data in order, either from smallest to largest or from largest to smallest.
1. Bubble Sort
Simple but slow.
[Idea] Compare adjacent numbers and push the larger one to the right.
def bubble_sort_example(arr):
a = arr[:] # keep original
n = len(a)
for end in range(n-1, 0, -1):
swap_flag = False
for i in range(end):
if a[i] > a[i+1]: # compare
a[i], a[i+1] = a[i+1], a[i]
swap_flag = True
if not swap_flag: # early exit
break
return a
print(bubble_sort_example([6, 4, 3, 7, 1, 9, 8]))
'''
Step-by-step execution:
1. (6, 4) compare and swap => (4, 6, 3, 7, 1, 9, 8)
2. (6, 3) compare and swap => (4, 3, 6, 7, 1, 9, 8)
3. (6, 7) no swap
... repeat
result = [1, 3, 4, 6, 7, 8, 9]
'''2. Selection Sort
Fewer swaps, but many comparisons.
[Idea] At each step i, find the minimun in the remaining range and swap it into position i.
def selection_sort_example(arr):
a = arr[:]
n = len(a)
for i in range(n-1): # find the smallest element
min_idx = i
for j in range(i+1, n):
if a[j] < a[min_idx]: # compare
min_idx = j
if min_idx != i: # swap
a[i], a[min_idx] = a[min_idx], a[i]
return a
print(selection_sort_example([6, 4, 3, 7, 1, 9, 8]))
'''
Step-by-step execution:
1. min_idx = 0, arr=[6, 4, 3, 7, 1, 9, 8] => min_idx = 4 => swap (6, 1) => (1, 4, 3, 7, 6, 9, 8)
2. min_idx = 1, arr=[1, 4, 3, 7, 6, 9, 8] => min_idx = 2 => swap (4, 3) => (1, 3, 4, 7, 6, 9, 8)
3. min_idx = 2, arr=[1, 3, 4, 7, 6, 9, 8] => min_idx = 2 => no swap
... repeat
result = [1, 3, 4, 6, 7, 8, 9]
'''
3. Insertion Sort
More efficient when the data is nearly sorted (because the cost grows with the number of inversions).
[Idea] Treat the left part as already sorted and insert the new key into its correct position.
def insertion_sort_example(arr):
a = arr[:]
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j+1] = a[j] # move to the right
j -= 1
a[j+1] = key # insert at the empty space
return a
print(insertion_sort_example([6, 4, 3, 7, 1, 9, 8]))
'''
Step-by-step execution:
1. key = 4, j = 0, a[j] > key => a[j+1] = a[j] => (6, 6, 3, 7, 1, 9, 8) => j-1, a[j+1] = key => (6, 4, 3, 7, 1, 9, 8)
2. key = 3, j = 1, a[j] > key => a[j+1] = a[j] => (6, 4, 4, 7, 1, 9, 8) => j-1, a[j+1] = key => (6, 3, 4, 7, 1, 9, 8)
3. key = 3, j = 0, a[j] > key => a[j+1] = a[j] => (3, 6, 4, 7, 1, 9, 8) => j-1, a[j+1] = key => (3, 6, 4, 7, 1, 9, 8)
4. key = 7, j = 2, a[j] > key => a[j+1] = a[j] => (3, 6, 4, 4, 1, 9, 8) => j-1, a[j+1] = key => (3, 6, 7, 4, 1, 9, 8)
... repeat
result = [1, 3, 4, 6, 7, 8, 9]
'''
4. Merge Sort
Always O(n log n) and stable, but it use extra (auxiliary) memory.
[Idea] Split the array in half, then merge two sorted halves.
def merge_sort_example(arr):
if len(arr) <= 1:
return arr[:]
# split
mid = len(arr)//2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# merge
merged = []
i = j = 0
while i < len(left) and j < len(right): # start from the first element and last element
if left[i] <= right[j]: # compare
merged.append(left[i]); i += 1
else:
merged.append(right[j]); j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return merged
print(merge_sort_example([6, 4, 3, 7, 1, 9, 8]))
'''
Step-by-step execution:
1. split [6, 4, 3, 7, 1, 9, 8] => [6, 4, 3, 7], [1, 9, 8]
2. split [6, 4, 3, 7] => [6, 4], [3, 7]
3. split [6, 4] => [6], [4]
4. split [3, 7] => [3], [7]
5. merge [6, 4] => [4, 6]
6. merge [3, 7] => [3, 7]
7. merge [4, 6, 3, 7] => [3, 4, 6, 7]
... repeat
result = [1, 3, 4, 6, 7, 8, 9]
'''
5. Quick Sort
Recursively sorts the partitioned parts; generally fast.
[Idea] Select a pivot and partition : values <= pivot go left, larger values go right.
Steps:
1. Place the pivot at the end and gather values <= pivot to the left (with swaps)
2. Move the pivot to its final positoin; then recursively sort the left and right subarrays.
def quick_sort_example(arr):
a = arr[:]
def partition(lo, hi): # split
pivot = a[hi]
i = lo - 1
for j in range(lo, hi):
if a[j] <= pivot:
i += 1
a[i], a[j] = a[j], a[i]
a[i+1], a[hi] = a[hi], a[i+1]
return i+1
def qs(lo, hi): # recursive
if lo < hi:
p = partition(lo, hi)
qs(lo, p-1)
qs(p+1, hi)
qs(0, len(a)-1)
return a
print(quick_sort_example([6, 4, 3, 7, 1, 9, 8]))
'''
Step-by-step execution:
1. split [6, 4, 3, 7, 1, 9, 8] => [6, 4, 3, 7], [1, 9, 8]
2. split [6, 4, 3, 7] => [6, 4], [3, 7]
3. split [6, 4] => [6], [4]
4. split [1, 9, 8] => [1, 9], [8]
5. split [1, 9] => [1], [9]
6. merge [6, 4] => [4, 6]
7. merge [3, 7] => [3, 7]
8. merge [1, 9] => [1, 9]
9. merge [4, 6, 3, 7, 1, 9, 8] => [1, 3, 4, 6, 7, 8, 9]
result = [1, 3, 4, 6, 7, 8, 9]
'''
6. Heap Sort
Guarantees O(n log n) even in the worst case.
[Idea] Build a max-heap, swap the root(maximum) with the end, shrink the heap, and repeat heapify.
def heap_sort_example(arr):
a = arr[:]
n = len(a)
def heapify(n, i): # make max heap
largest = i
l = 2*i + 1
r = 2*i + 2
if l < n and a[l] > a[largest]:
largest = l
if r < n and a[r] > a[largest]:
largest = r
if largest != i:
a[i], a[largest] = a[largest], a[i] # swap
heapify(n, largest)
# make max heap
for i in range(n//2 - 1, -1, -1):
heapify(n, i)
# keep heap
for end in range(n-1, 0, -1):
a[0], a[end] = a[end], a[0]
heapify(end, 0)
return a
print(heap_sort_example([6, 4, 3, 7, 1, 9, 8]))
'''
Step-by-step execution:
1. heapify(7, 2) => l = 5, r = 6, largest = 2 ⇒ swap(2,5)
2. heapify(7, 5) => l = 11, r = 12, largest = 5 ⇒ [6, 4, 9, 7, 1, 3, 8]
3. heapify(7, 1) => l = 3, r = 4, largest = 1 ⇒ swap(1,3)
4. heapify(7, 3) => l = 7, r = 8, largest = 3 ⇒ [6, 7, 9, 4, 1, 3, 8]
...repeat
result = [1, 3, 4, 6, 7, 8, 9]
'''
Conclusion
Slow : Bubble, Selection, Insertion -> O(n^2)
Fast : Merge, Quick, Heap -> O(n log n)
Reference
https://en.wikipedia.org/wiki/Sorting_algorithm
'CS' 카테고리의 다른 글
| MIT 6.034 Study Notes — Week 1~4 (0) | 2025.10.29 |
|---|---|
| Graph algorithms (0) | 2025.09.21 |
| Data Structures (0) | 2025.09.10 |
| Complexity Analysis - Asymptotic notation & Time/Space Trade-off (0) | 2025.09.01 |
| Complexity Analysis - Time Complexity (0) | 2025.08.29 |