Sorting Algorithms

Sorting algorithms are fundamental to computer science, used to arrange data in a particular order. This blog will cover six common sorting algorithms: Bubble Sort, Merge Sort, Quick Sort, Insertion Sort, Selection Sort, and Heap Sort. Each algorithm has its unique approach and use case. I’ll provide detailed explanations and Python implementations for each.

Bubble Sort Algorithm

Bubble Sort is a simple comparison-based algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process repeats until the list is sorted.

How it works:

1. Start at the beginning of the list.

2. Compare the first two elements; if the first is greater than the second, swap them.

3. Move to the next pair of elements and repeat the process.

4. Continue until the end of the list.

5. Repeat the entire process for the remaining elements.

Python Code:

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]

# Example usage
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Sorted array is:", arr)

Merge Sort Algorithm

Merge Sort is a divide-and-conquer algorithm. It divides the array into two halves, recursively sorts them, and then merges the sorted halves.

How it works:

1. Divide the array into two halves.

2. Recursively sort each half.

3. Merge the two halves to produce the sorted array.

Python Code:

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

# Example usage
arr = [12, 11, 13, 5, 6, 7]
merge_sort(arr)
print("Sorted array is:", arr)

Quick Sort Algorithm

Quick Sort is another divide-and-conquer algorithm. It picks an element as a pivot and partitions the array around the pivot.

How it works:

1. Pick a pivot element.

2. Partition the array into two halves based on the pivot.

3. Recursively apply the same process to the two halves.

Python Code:

def partition(arr, low, high):
    i = (low-1)
    pivot = arr[high]

    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)

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)

# Example usage
arr = [10, 7, 8, 9, 1, 5]
quick_sort(arr, 0, len(arr)-1)
print("Sorted array is:", arr)

Insertion Sort Algorithm

Insertion Sort builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as Quick Sort, Merge Sort, or Heap Sort.

How it works:

1. Start with the second element. Assume the first element is already sorted.

2. Compare the current element with the sorted elements and insert it in the correct position.

3. Repeat until the entire array is sorted.

Python Code:

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

# Example usage
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print("Sorted array is:", arr)

Selection Sort Algorithm

Selection Sort divides the input list into two parts: the sorted part and the unsorted part. It repeatedly selects the smallest (or largest) element from the unsorted part and moves it to the sorted part.

How it works:

1. Find the minimum element in the unsorted part.

2. Swap it with the first unsorted element.

3. Move the boundary between the sorted and unsorted parts one element to the right.

4. Repeat until the entire array is sorted.

Python Code:

def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

# Example usage
arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("Sorted array is:", arr)

Heap Sort Algorithm

Heap Sort is a comparison-based sorting technique based on a binary heap data structure. It is similar to selection sort where we first find the maximum element and place it at the end. We repeat the same process for the remaining elements.

How it works:

1. Build a max heap from the input data.

2. The largest item is stored at the root of the heap. Replace it with the last item of the heap and reduce the heap size by one.

3. Heapify the root of the tree.

4. Repeat step 2 until the heap size is reduced to one.

Python Code:

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)

# Example usage
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("Sorted array is:", arr)

Sorting algorithms are essential tools in programming and computer science. Each algorithm has its strengths and weaknesses, making them suitable for different scenarios. By understanding how these algorithms work and implementing them in Python, you can choose the best one for your specific needs.