Spaces:
Sleeping
Sleeping
File size: 5,037 Bytes
4a3f117 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 | SORTING ALGORITHMS
==================
--- Bubble Sort ---
Repeatedly compare adjacent elements and swap if out of order. Largest element bubbles to end each pass.
Time: O(n^2) average/worst, O(n) best (already sorted). Space: O(1). Stable.
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break # already sorted
return arr
print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))
# Output: [11, 12, 22, 25, 34, 64, 90]
--- Selection Sort ---
Find the minimum element and place it at the beginning. Repeat for remaining array.
Time: O(n^2) all cases. Space: O(1). Not stable.
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
print(selection_sort([64, 25, 12, 22, 11]))
# Output: [11, 12, 22, 25, 64]
--- Insertion Sort ---
Build sorted array one element at a time. Take each element and insert it into the correct position.
Time: O(n^2) worst, O(n) best. Space: O(1). Stable. Best for small or nearly sorted data.
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
print(insertion_sort([12, 11, 13, 5, 6]))
# Output: [5, 6, 11, 12, 13]
--- Merge Sort ---
Divide array in half, recursively sort both halves, then merge the sorted halves.
Time: O(n log n) all cases. Space: O(n). Stable. Best for linked lists and large datasets.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# Output: [3, 9, 10, 27, 38, 43, 82]
--- Quick Sort ---
Pick a pivot, partition array so all elements less than pivot are on left, greater on right. Recurse.
Time: O(n log n) average, O(n^2) worst. Space: O(log n). Not stable. Fastest in practice.
def quick_sort(arr, low=0, high=None):
if high is None:
high = len(arr) - 1
if low < high:
pi = partition(arr, low, high)
quick_sort(arr, low, pi - 1)
quick_sort(arr, pi + 1, high)
return arr
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
print(quick_sort([10, 7, 8, 9, 1, 5]))
# Output: [1, 5, 7, 8, 9, 10]
--- Heap Sort ---
Build a max-heap from the array. Repeatedly extract the maximum and place at end.
Time: O(n log n) all cases. Space: O(1). Not stable.
def heap_sort(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
return arr
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
print(heap_sort([12, 11, 13, 5, 6, 7]))
# Output: [5, 6, 7, 11, 12, 13]
--- Counting Sort ---
Count occurrences of each element. Works only on non-negative integers within a known range.
Time: O(n + k) where k is the range. Space: O(k). Stable.
def counting_sort(arr):
if not arr:
return arr
max_val = max(arr)
count = [0] * (max_val + 1)
for num in arr:
count[num] += 1
result = []
for i, c in enumerate(count):
result.extend([i] * c)
return result
print(counting_sort([4, 2, 2, 8, 3, 3, 1]))
# Output: [1, 2, 2, 3, 3, 4, 8]
--- Comparison Summary ---
Algorithm | Best | Average | Worst | Space | 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
Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes
|