Sorting
Quicksort is a Divide and Conquer algorithm.
Divide (Pick Pivot): Choose one element from the array to be the pivot. Conquer (Partition): Rearrange the array so that the pivot is in its final sorted position. All elements smaller than the pivot are placed to its left, and all elements greater than the pivot are placed to its right. (Elements equal to the pivot can go on either side, depending on the scheme). Combine (Recurse): Recursively apply the same strategy to the two smaller subarrays—the one to the left of the pivot’s new position and the one to the right. The “combine” step is trivial as the sorting happens in place. def partition(a, left, right): """ Partitions the subarray a[left...right] using the Lomuto scheme with a[left] as the pivot. Returns the final index of the pivot. """ # The pivot is the first element pivot_value = a[left] # 'idx' will track the boundary of the 'less-than-or-equal-to' partition. # All elements at indices [left+1 ... idx-1] will be <= pivot. idx = left + 1 # Iterate through the array to partition it for i in range(left + 1, right + 1): # If current element is smaller or equal to the pivot if a[i] <= pivot_value: # Move it to the 'less-than' partition a[idx], a[i] = a[i], a[idx] # Expand the 'less-than' partition idx += 1 # At the end, swap the pivot (originally at a[left]) with # the last element of the 'less-than' partition (at a[idx - 1]) # to put the pivot in its final sorted position. pivot_final_index = idx - 1 a[left], a[pivot_final_index] = a[pivot_final_index], a[left] return pivot_final_index def quicksort(a, left, right): """ Sorts the array 'a' in-place from index 'left' to 'right' using the quicksort algorithm. """ if left < right: # Partition the array and get the pivot's final index pivot_index = partition(a, left, right) # Recursively sort the two subarrays quicksort(a, left, pivot_index - 1) # Subarray to the left of pivot quicksort(a, pivot_index + 1, right) # Subarray to the right of pivot
Read note →The algorithm breaks the problem down into smaller, manageable pieces and then reassembles them in a sorted order. This happens in three main phases:
Divide: The list is repeatedly divided in half until you are left with many small lists, each containing only one element. A list with one element is considered, by definition, to be sorted (this is the base case for the recursion). Conquer: This phase is trivial. Since the base-case lists (of one element) are already sorted, there’s no work to do. The real work happens in the “Combine” step. Combine (The “Merge”): This is the core of the algorithm. Merge sort begins to combine (or “merge”) the small, one-element lists back together, two at a time. Crucially, it merges them in sorted order. It then takes those newly sorted lists (now of 2 elements) and merges them together, and so on, until the entire list is reassembled into one final, sorted list. def merge_sort(arr): """ Sorts a list in ascending order using the merge sort algorithm. """ # Base case: A list with 0 or 1 elements is already sorted if len(arr) <= 1: return arr # 1. Divide: Split the list into two halves mid = len(arr) // 2 left_half = arr[:mid] right_half = arr[mid:] # 2. Conquer: Recursively sort each half sorted_left = merge_sort(left_half) sorted_right = merge_sort(right_half) # 3. Combine: Merge the two sorted halves merged = [] i = 0 # Pointer for sorted_left j = 0 # Pointer for sorted_right # Loop while both halves have elements to compare while i < len(sorted_left) and j < len(sorted_right): if sorted_left[i] < sorted_right[j]: merged.append(sorted_left[i]) i += 1 else: merged.append(sorted_right[j]) j += 1 # At this point, one of the halves is empty. # Add all remaining elements from the non-empty half. merged.extend(sorted_left[i:]) merged.extend(sorted_right[j:]) return merged # --- Example Usage --- my_list = [38, 27, 43, 3, 9, 82, 10] print(f"Original list: {my_list}") sorted_list = merge_sort(my_list) print(f"Sorted list: {sorted_list}")
Read note →Bucket sort is a non-comparison sorting algorithm that works by distributing the elements of an array into a number of “buckets.” It is highly efficient when the input data is uniformly distributed (i.e., spread out evenly) across its range.
The algorithm follows these four main steps:
Initialize Buckets: First, create a fixed number of empty buckets (in your case, bucket_count). Scatter: Iterate through the input array. For each element, calculate its proper bucket index (based on its value relative to the min/max values) and place the element into that bucket. Sort Buckets: Go through each bucket, one by one, and sort the elements within it. This is typically done using another algorithm like insertion sort (or, in this case, Python’s built-in sort()). Gather: Finally, concatenate the sorted buckets in order (from bucket 0 to the last bucket) to reassemble the full, sorted array. from itertools import chain def bucket_sort(arr, bucket_count): """ Sorts a list in ascending order using the bucket sort algorithm. """ # 1. Edge case: Handle empty or single-element lists if len(arr) <= 1: return arr # 2. Initialize Buckets & Find Range min_val, max_val = min(arr), max(arr) # Edge case: If all elements are the same, no sorting needed if min_val == max_val: return arr # Calculate the size of each bucket. # The '+1' ensures the range [min_val, max_val] is covered. bucket_size = (max_val - min_val + 1) // bucket_count # Fix for bucket_size becoming 0 if bucket_count > (max_val - min_val) if bucket_size == 0: bucket_size = 1 buckets = [[] for _ in range(bucket_count)] # 3. Scatter: Distribute elements into buckets for x in arr: # Calculate the bucket index for the element idx = (x - min_val) // bucket_size # CRITICAL FIX: Ensure max_val lands in the last bucket idx = min(idx, bucket_count - 1) buckets[idx].append(x) # 4. Sort Buckets: Sort each individual bucket for bucket in buckets: bucket.sort() # Using built-in sort (Timsort) # 5. Gather: Concatenate the sorted buckets return list(chain(*buckets)) # --- Example Usage --- my_list = [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51] # Using bucket_count = 5 sorted_list = bucket_sort(my_list, 5) print(f"Original list: {my_list}") print(f"Sorted list: {sorted_list}") my_list_2 = [29, 25, 3, 49, 9, 37, 21, 43] # Using bucket_count = 4 sorted_list_2 = bucket_sort(my_list_2, 4) print(f"\nOriginal list: {my_list_2}") print(f"Sorted list: {sorted_list_2}")
Read note →Selection sort works by conceptually dividing the list into two parts:
A sorted subarray, which is built up from left to right at the beginning. An unsorted subarray, which makes up the rest of the list. The algorithm iterates through the list, and at each step $i$ (from $i = 0$ to $n-1$): Find: It finds the smallest element in the unsorted subarray (i.e., from index $i$ to the end). Swap: It swaps that smallest element with the element at the first position of the unsorted subarray (which is index $i$). def selection_sort(arr): """ Sorts a list in ascending order using the selection sort algorithm. """ n = len(arr) # Outer loop: Move the boundary of the sorted subarray # This corresponds to your "i-th position" for i in range(n): # Step 1: Find the index of the smallest element in the # remaining unsorted part (from index i to n-1) min_index = i for j in range(i + 1, n): if arr[j] < arr[min_index]: min_index = j # Step 2: Swap the found smallest element with the # element at the i-th position # This "puts the smallest element" into its final sorted place arr[i], arr[min_index] = arr[min_index], arr[i] # --- Example Usage --- my_list = [64, 25, 12, 22, 11] print(f"Original list: {my_list}") selection_sort(my_list) print(f"Sorted list: {my_list}")
Read note →Start with the second element (at index 1), assuming the first element (at index 0) is already a sorted list of one. Store this current element in a temporary variable (let’s call it the key). Compare the key with the elements in the sorted subarray, moving from right to left (i.e., from index $i-1$ down to 0). Shift any element in the sorted subarray that is greater than the key one position to the right. This opens up a “gap” for the key. Insert the key into the gap once you find an element smaller than it, or when you reach the beginning of the list. Repeat this process, expanding the sorted subarray by one element each time, until the entire list is sorted. def insertion_sort(arr): """ Sorts a list in ascending order using the insertion sort algorithm. """ # Start from the second element (index 1) # The first element (index 0) is treated as the initial sorted part for i in range(1, len(arr)): # Step 2: Store the current element to be inserted key = arr[i] # Step 3 & 4: Move elements of the sorted part (arr[0..i-1]) # that are greater than key, one position to the right j = i - 1 while j >= 0 and key < arr[j]: arr[j + 1] = arr[j] # Shift element to the right j -= 1 # Step 5: Insert the key into its correct position arr[j + 1] = key # --- Example Usage --- my_list = [12, 11, 13, 5, 6] print(f"Original list: {my_list}") insertion_sort(my_list) print(f"Sorted list: {my_list}")
Read note →Make a “pass” through the unsorted part of the list, comparing every pair of adjacent items (from the beginning to the end of the unsorted section). For each pair, if the item on the left is greater than the item on the right, swap them. This moves the larger element one position to the right. After the first full pass, the largest element in the list will have “bubbled up” to the very last position. Repeat the process for the remaining unsorted portion of the list (i.e., from the beginning up to the now-sorted end), making one less comparison each time. Continue until no more swaps are needed. def bubble_sort(arr): """ Sorts a list in ascending order using the bubble sort algorithm. """ n = len(arr) # Outer loop for the number of passes for i in range(n): # A flag to optimize if the list becomes sorted early swapped = False # Inner loop for comparing adjacent elements # The range is (n-i-1) because the last 'i' elements are already in place for j in range(0, n - i - 1): # Compare adjacent elements if arr[j] > arr[j + 1]: # Swap them if the first is greater than the second arr[j], arr[j + 1] = arr[j + 1], arr[j] swapped = True # If no swaps occurred in a full pass, the list is sorted if not swapped: break # --- Example Usage --- my_list = [64, 34, 25, 12, 22, 11, 90] print(f"Original list: {my_list}") bubble_sort(my_list) print(f"Sorted list: {my_list}")
Read note →