Sorting algorithms are a fundamental part of computer science and are used to arrange a list of elements in a specific order. There are numerous sorting algorithms available, each with its own set of strengths and weaknesses. In this blog, we will discuss the most common sorting algorithms and their implementations.
1. Bubble Sort:
Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The algorithm gets its name from the way smaller elements "bubble" to the top of the list.
Here's an implementation of Bubble Sort in Python:
def bubbleSort(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]
2. Selection Sort:
Selection sort is an algorithm that sorts an array by repeatedly finding the minimum element from the unsorted part of the array and putting it at the beginning. It has a complexity of O(n^2).
Here's an implementation of Selection Sort in Python:
def selectionSort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if arr[min_idx] > arr[j]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
3. Insertion Sort:
Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. It has a complexity of O(n^2).
Here's an implementation of Insertion Sort in Python:
def insertionSort(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
4. Quick Sort:
Quick sort is a divide and conquer algorithm that picks an element as a pivot and partitions the array around the pivot, putting all elements smaller than the pivot to its left and all elements greater than the pivot to its right. It then recursively sorts the two subarrays. It has a complexity of O(nlogn).
Here's an implementation of Quick Sort in Python:
def partition(arr, low, high):
i = (low-1)
pivot = arr[high]
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 quickSort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)
5. Merge Sort:
Merge sort is a divide and conquer algorithm that divides the array into two halves, recursively sorts the two halves, and then merges the sorted halves. It has a complexity of O(nlogn).
Here's an implementation of Merge Sort in Python:
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
# Recursive calls to divide the array into smaller subarrays
merge_sort(left_half)
merge_sort(right_half)
i = j = k = 0
# Merge the subarrays
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
# Example usage
arr = [6, 5, 3, 1, 8, 7, 2, 4]
merge_sort(arr)
print(arr) # Output: [1, 2, 3, 4, 5, 6, 7, 8]
6. Heap Sort:
Heap sort is a comparison-based sorting algorithm that works by first building a binary heap from the array to be sorted, and then repeatedly extracting the maximum element from the heap and putting it at the end of the array until the heap is empty. The heap is built in such a way that the root node of each subtree has a larger value than its children (in a max-heap), or a smaller value (in a min-heap).
The steps to perform heap sort are:
- Build a max heap from the input array.
- Extract the maximum element from the heap (which is always the root element) and swap it with the last element of the heap.
- Reduce the heap size by one and heapify the root of the heap (which is now the last element of the heap).
- Repeat steps 2 and 3 until the heap is empty.
Here's the algorithm in more detail:
def heapify(arr, n, i):
"""
A helper function that heapifies a subtree rooted with node i
in a given array arr of size n.
"""
largest = i
l = 2 * i + 1
r = 2 * i + 2
# If left child is larger than root
if l < n and arr[l] > arr[largest]:
largest = l
# If right child is larger than largest so far
if r < n and arr[r] > arr[largest]:
largest = r
# If largest is not root
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # Swap root with largest child
# Recursively heapify the affected sub-tree
heapify(arr, n, largest)
def heap_sort(arr):
"""
A function to perform Heap Sort on a given array arr.
"""
n = len(arr)
# Build a max-heap
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# Extract elements one by one
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0] # Swap the root with the last element
heapify(arr, i, 0)
return arr
You can use this function to sort a list by calling heap_sort(arr) where arr is the list to be sorted.
Top comments (0)