Spaces:
Sleeping
Sleeping
| 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 | |