Sorting Algorithms
You will learn about various sorting algorithms, including their basic principles, how they work, and their time complexities.
Bubble Sort
Principle: Bubble Sort is a simple comparison-based sorting algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process is repeated until the list is sorted.
How it Works:
- Start from the beginning of the array.
- Compare each pair of adjacent elements.
- Swap them if they are in the wrong order.
- Continue until no more swaps are needed, which means the list is sorted.
Time Complexity:
- Best Case: (O(n)) when the array is already sorted.
- Average Case: (O(n^2)).
- Worst Case: (O(n^2)).
def bubbleSort(arr):
n = len(arr)
swapped = False
for i in range(n-1):
for j in range(0, n-i-1):
if arr[j] > arr[j + 1]:
swapped = True
arr[j], arr[j + 1] = arr[j + 1], arr[j]
if not swapped:
return
arr = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(arr)
print("Sorted array is:")
for i in range(len(arr)):
print("% d" % arr[i], end=" ")How it works
swap and Bubble to the right
[9,7,12,9,45,97,38]compare 9 & 7 and swap smallest to the left
[7,9,12,9,45,97,38]Compare 9 & 12 and swap smallest to the left
[7,9,12,9,45,97,38]Compare 12 and 9 and swap smallest to the left
[7,9,9,12,45,97,38]Compare 12 and 45 and swap smallest to the left
[7,9,9,12,45,97,38]Compare 45 and 97 and swap smallest to the left
[7,9,9,12,45,97,38]Compare 97 and 38 and swap smallest to the left
[7,9,9,12,45,38,97]Sorted!
Quick Sort
Principle: Quick Sort is a divide-and-conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot.
How it Works:
- Choose a pivot element.
- Partition the array so that all elements less than the pivot are on its left, and all greater elements are on its right.
- Recursively apply the above steps to the sub-arrays.
- Combine the sub-arrays to produce the sorted array.
Time Complexity:
- Best Case: (O(n \log n)).
- Average Case: (O(n \log n)).
- Worst Case: (O(n^2)) (when the smallest or largest element is always chosen as the pivot).
def quicksort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
left = [x for x in arr[1:] if x < pivot]
right = [x for x in arr[1:] if x >= pivot]
return quicksort(left) + [pivot] + quicksort(right)
arr = [1, 7, 4, 1, 10, 9, -2]
sorted_arr = quicksort(arr)
print("Sorted Array in Ascending Order:")
print(sorted_arr)How it works
A divide and conquer algorithm
- If the input array has length 0 or 1, return the array as it is already sorted.
- Choose the first element of the array as the pivot element.
- Create two empty lists, left and right.
- For each element in the array except for the pivot:
- a. If the element is smaller than the pivot, add it to the left list.
- b. If the element is greater than or equal to the pivot, add it to the right list.
- Recursively call quicksort on the left and right lists.
- Concatenate the sorted left list, the pivot element, and the sorted right list.
- Return the concatenated list.
Insertion Sort
Principle: Insertion Sort builds the sorted array one item at a time. It takes each element from the input and inserts it into its correct position in a growing sorted list.
How it Works:
- Begin with the second element, and compare it to the elements before it.
- Insert it in its correct position by shifting elements as needed.
- Repeat for all elements in the array.
Time Complexity:
- Best Case: (O(n)) when the array is already sorted.
- Average Case: (O(n^2)).
- Worst Case: (O(n^2)).
def insertionSort(arr):
n = len(arr) # Get the length of the array
if n <= 1:
return
for i in range(1, n):
key = arr[i]
j = i-1
while j >= 0 and key < arr[j]:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
arr = [12, 11, 13, 5, 6]
insertionSort(arr)
print(arr)Bogo Sort
Principle: Bogo Sort, also known as permutation sort or stupid sort, is based on generating random permutations of the array until it is sorted. It is not practical for large arrays due to its inefficiency.
How it Works:
- Randomly shuffle the array.
- Check if the array is sorted.
- Repeat until the array is sorted.
Time Complexity:
- Average and Worst Case: (O((n+1)!)).
Merge Sort
Principle: Merge Sort is a divide-and-conquer algorithm that splits the array into halves, sorts each half, and then merges the sorted halves.
How it Works:
- Divide the array into two halves.
- Recursively sort each half.
- Merge the two sorted halves to produce a single sorted array.
Time Complexity:
- Best Case: (O(n \log n)).
- Average Case: (O(n \log n)).
- Worst Case: (O(n \log n)).
def merge_sort(array):
if len(array) > 1:
# Find the middle index
middle_index = len(array) // 2
# Divide the array elements into two halves
left_half = array[:middle_index]
right_half = array[middle_index:]
# Sort the first and second halves
merge_sort(left_half)
merge_sort(right_half)
# Initialize indices for left_half, right_half, and merged array
left_index = right_index = merged_index = 0
# Merge the sorted halves back into the original array
while left_index < len(left_half) and right_index < len(right_half):
if left_half[left_index] < right_half[right_index]:
array[merged_index] = left_half[left_index]
left_index += 1
else:
array[merged_index] = right_half[right_index]
right_index += 1
merged_index += 1
# Check if any elements were left in the left_half
while left_index < len(left_half):
array[merged_index] = left_half[left_index]
left_index += 1
merged_index += 1
# Check if any elements were left in the right_half
while right_index < len(right_half):
array[merged_index] = right_half[right_index]
right_index += 1
merged_index += 1
# Example usage
array_to_sort = [12, 11, 13, 5, 6, 7]
merge_sort(array_to_sort)
print("Sorted array is:", array_to_sort)Heap Sort
Principle: Heap Sort uses a binary heap data structure to sort an array. It transforms the array into a max heap, then repeatedly extracts the maximum element and rebuilds the heap until the array is sorted.
How it Works:
- Build a max heap from the array.
- Swap the root (maximum value) with the last item.
- Reduce the size of the heap and heapify the root.
- Repeat until the heap is empty.
Time Complexity:
- Best Case: (O(n \log n)).
- Average Case: (O(n \log n)).
- Worst Case: (O(n \log n)).
def heapify(array, heap_size, root_index):
largest_index = root_index
left_child_index = 2 * root_index + 1
right_child_index = 2 * root_index + 2
# Check if the left child exists and is greater than root
if left_child_index < heap_size and array[root_index] < array[left_child_index]:
largest_index = left_child_index
# Check if the right child exists and is greater than largest so far
if right_child_index < heap_size and array[largest_index] < array[right_child_index]:
largest_index = right_child_index
# Change root, if needed
if largest_index != root_index:
array[root_index], array[largest_index] = array[largest_index], array[root_index] # Swap
heapify(array, heap_size, largest_index)
def heap_sort(array):
array_size = len(array)
# Build a max heap
for root_index in range(array_size // 2 - 1, -1, -1):
heapify(array, array_size, root_index)
# Extract elements one by one from the heap
for end_index in range(array_size - 1, 0, -1):
array[end_index], array[0] = array[0], array[end_index] # Swap
heapify(array, end_index, 0)
# Example usage
array_to_sort = [12, 11, 13, 5, 6, 7]
heap_sort(array_to_sort)
print("Sorted array is:", array_to_sort)Selection Sort
Principle: Selection Sort divides the input list into two parts: a sorted part and an unsorted part. It repeatedly selects the smallest element from the unsorted part and swaps it with the first unsorted element.
How it Works:
- Find the minimum element from the unsorted part of the array.
- Swap it with the first unsorted element.
- Move the boundary between the sorted and unsorted parts by one.
- Repeat until the entire array is sorted.
Time Complexity:
- Best Case: (O(n^2)).
- Average Case: (O(n^2)).
- Worst Case: (O(n^2)).
def selectionSort(array, size):
for ind in range(size):
min_index = ind
for j in range(ind + 1, size):
# select the minimum element in every iteration
if array[j] < array[min_index]:
min_index = j
# swapping the elements
(array[ind], array[min_index]) = (array[min_index], array[ind])
arr = [-2, 45, 0, 11, -9,88,-97,-202,747]
size = len(arr)
selectionSort(arr, size)
print(f'The array after sorting in Ascending Order by selection sort is: {arr}')How it works
Scan all items and find the smallest. Swap it into position as the first item. Repeat the selection sort on the remaining N-1 items.
[7,9,9,12,45,38,97]Loop through list and find smallest number (save current smallest)
Set as first item in the list
Scan other items and find the smallest,
Radix Sort
Principle: Radix Sort is a non-comparative integer sorting algorithm. It sorts numbers by processing individual digits. It uses counting sort as a subroutine to sort digits at each position.
How it Works:
- Process each digit of the numbers from the least significant to the most significant (LSD) or vice versa (MSD).
- Use counting sort to sort numbers based on each digit.
- Repeat for all digit positions.
Time Complexity:
- Best, Average, and Worst Case: (O(nk)), where (n) is the number of elements and (k) is the number of digits in the largest number.
def counting_sort_for_radix(array, exponent):
array_size = len(array)
output_array = [0] * array_size # Output array that will have sorted array
count_array = [0] * 10 # Count array to store count of occurrences
# Store count of occurrences in count_array
for number in array:
digit = (number // exponent) % 10
count_array[digit] += 1
# Change count_array[i] so it contains the actual position of this digit in output_array
for i in range(1, 10):
count_array[i] += count_array[i - 1]
# Build the output array
for index in range(array_size - 1, -1, -1):
digit = (array[index] // exponent) % 10
output_array[count_array[digit] - 1] = array[index]
count_array[digit] -= 1
# Copy the output array to array[], so that array now contains sorted numbers
for index in range(array_size):
array[index] = output_array[index]
def radix_sort(array):
# Find the maximum number to know the number of digits
max_number = max(array)
# Do counting sort for every digit. Instead of passing digit number, exponent is passed. Exponent is 10^i where i is the current digit number
exponent = 1
while max_number // exponent > 0:
counting_sort_for_radix(array, exponent)
exponent *= 10
# Example usage
array_to_sort = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(array_to_sort)
print("Sorted array is:", array_to_sort)Summary
- Simple and Slow: Bubble Sort, Insertion Sort, Selection Sort are simple but inefficient for large datasets due to their (O(n^2)) time complexity.
- Efficient: Quick Sort, Merge Sort, and Heap Sort are more efficient, with an average time complexity of (O(n \log n)).
- Specialized: Radix Sort is efficient for numbers with fixed digit lengths, while Bogo Sort is more of a joke algorithm due to its impracticality.
These sorting algorithms each have their own use cases and trade-offs in terms of complexity and efficiency, making them suitable for different scenarios.