Sorting is fundamental operation in computer science, used in various application ranging from database query optimization to data analysis. Efficient sorting algorithms can make a significant difference in performance, especially with large datasets. In this blog post, we will explore the most common sorting algorithms, understand their working principles, and analyze their time complexities.
Why Sorting?
Sorting is crucial because it:
- Organizes Data: Makes it easier to search, access, and analyze data.
- Enhances Efficiency: Improves the performance of other algorithms, such as search algorithms, which benefit from sorted data (Binary search..)
- Facilitates Data representation: Helps in presenting data in a reachable and understandable format.
Common Sorting Algorithms
Bubble Sort
Bubble Sort is a simple comparation-based algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Sorted array is:", arr)
Time complexity
- Worst-case: O(N^2)
- Best-base: O(N) When array is already sorted.
Selection Sort
Selection Sort divides the array into a sorted and an unsorted region. It repeatedly selects the smallest(or largest) element from the unsorted region and moves it to the end of the sorted region.
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]
arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("Sorted array is:", arr)
Time Complexity
- Worst-case and Best-case O(n^2)
Insertion Sort
Insertion Sort builds the final sorted array one item at a time. It takes each element from the input and finds the correct location within the sorted portion of the array.
def insertion_sort(arr):
for i in range(1, len(arr)):
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]
insertion_sort(arr)
print("Sorted array is:", arr)
Time Complexity
- Worst-case O(N^2)
- Best-case O(N) when the array is already sorted
Merge Sort
Merge Sort is a divide-and-conquer algorithm. It divides the array into halves, recursively sorts them, and them merges the sorted halves.
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
L = arr[:mid]
R = arr[mid:]
merge_sort(L)
merge_sort(R)
i = j = k = 0
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
arr = [12, 11, 13, 5, 6, 7]
merge_sort(arr)
print("Sorted array is:", arr)
Time Complexity
Worst-case and Base-case O(NLogN)
Quick Sort
Quick sort is another divide-and-conquer algorithm. It selects a ‘pivot’ element and partitions the array into elements less than the pivot and elements greater than the pivot, than recursively sorts the partitions
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i = i + 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quick_sort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quick_sort(arr, low, pi - 1)
quick_sort(arr, pi + 1, high)
arr = [10, 7, 8, 9, 1, 5]
quick_sort(arr, 0, len(arr) - 1)
print("Sorted array is:", arr)
Heap Sort
Heap Sort uses a binary heap data structure to sort elements. It converts the array into a heap, repeatedly extracts the maximum elements and rebuild the heap.
def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
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[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("Sorted array is:", arr)
Time complexity
- Worst-case and Best-case: O(NlogN)
Radix Sort
Radix Sort processes individual digits of the numbers. It sorts numbers digit by digit, starting from the least significant digit to the most significant digit.
def counting_sort(arr, exp1):
n = len(arr)
output = [0] * (n)
count = [0] * (10)
for i in range(0, n):
index = (arr[i] // exp1)
count[(index) % 10] += 1
for i in range(1, 10):
count[i] += count[i - 1]
i = n - 1
while i >= 0:
index = (arr[i] // exp1)
output[count[(index) % 10] - 1] = arr[i]
count[(index) % 10] -= 1
i -= 1
i = 0
for i in range(0, len(arr)):
arr[i] = output[i]
def radix_sort(arr):
max1 = max(arr)
exp = 1
while max1 // exp > 0:
counting_sort(arr, exp)
exp *= 10
arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print("Sorted array is:", arr)
Time Complexity:
Worst-case and Best-case O(nk), where n is the number of elements and k is the number of digits in the largest number
Source code: https://github.com/hongquan080799/data-structure-and-algorithms
Conclusion
Sorting algorithms are essential tools in the toolkit of any programmer. Understanding the various sorting algorithms and their time complexities can help you choose the right one for your specific needs. Each algorithm has its strengths and weaknesses, making it suitable for different scenarios.
