Sorting Algorithms - From Classic to Modern

Introduction

As software engineers, we frequently encounter scenarios where sorting large sets of data becomes necessary. Sorting algorithms play a vital role in organizing information efficiently and effectively. In this blog post, we will dive deep into various sorting algorithms, discussing their principles, complexities, and use cases. Along the way, we'll provide illustrative examples with code snippets to enhance your understanding. So, let's embark on this journey and explore the fascinating world of sorting algorithms!

Table of Contents

1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Merge Sort
5. Quick Sort
6. Heap Sort
7. Radix Sort
8. Counting Sort
9. Comparison and Summary

Bubble Sort

Bubble Sort is one of the simplest sorting algorithms, making it an excellent starting point for our discussion. It works by repeatedly swapping adjacent elements if they are in the wrong order until the entire list is sorted. Although not the most efficient algorithm, Bubble Sort is easy to implement and comprehend.

Visualization

Complexity

Name	Best	Average	Worst	Memory	Stable	Comments
Bubble sort	n	n2	n2	1	Yes

Code Example

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]
    return arr

Selection Sort

Selection Sort operates by dividing the input list into a sorted and an unsorted portion. It repeatedly finds the minimum element from the unsorted portion and moves it to the sorted section. This process continues until the entire list is sorted.

Visualization

Complexity

Name	Best	Average	Worst	Memory	Stable	Comments
Selection sort	n2	n2	n2	1	No

Code Example

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

Insertion Sort

Insertion Sort builds the final sorted array one element at a time. It iterates through the list, comparing each element with the sorted portion and inserting it in the correct position. Insertion Sort is efficient for small datasets or partially sorted lists.

Visualization

Complexity

Name	Best	Average	Worst	Memory	Stable	Comments
Insertion sort	n	n2	n2	1	Yes

Code Example

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

Merge Sort

Merge Sort is a divide-and-conquer algorithm that divides the input list into smaller halves, sorts them independently, and merges them to obtain the final sorted list. It utilizes a recursive approach and is known for its stability and consistent performance across various scenarios.

Visualization

A recursive merge sort algorithm used to sort an array of 7
integer values. These are the steps a human would take to
emulate merge sort (top-down).

Complexity

Name	Best	Average	Worst	Memory	Stable	Comments
Merge sort	n log(n)	n log(n)	n log(n)	n	Yes

Code Example

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)
    return merge(left_half, right_half)

def merge(left, right):
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    while i < len(left):
        merged.append(left[i])
        i += 1
    while j < len(right):
        merged.append(right[j])
        j += 1
    return merged

Quick Sort

Quick Sort is another divide-and-conquer algorithm that partitions the list based on a chosen pivot element, arranging elements smaller than the pivot to its left and larger elements to its right. It then recursively sorts the left and right partitions. Quick Sort is known for its efficiency and is widely used in practice.

Visualization

Complexity

Name	Best	Average	Worst	Memory	Stable	Comments
Quick sort	n log(n)	n log(n)	n2	log(n)	No	Quicksort is usually done in-place with O(log(n)) stack space

Code Example

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    smaller, equal, larger = [], [], []
    for num in arr:
        if num < pivot:
            smaller.append(num)
        elif num == pivot:
            equal.append(num)
        else:
            larger.append(num)
    return quick_sort(smaller) + equal + quick_sort(larger)

Heap Sort

Heap Sort uses a binary heap data structure to sort elements. It first constructs a max-heap from the input list, then repeatedly extracts the maximum element (root) and places it at the end. The process is repeated until the entire list is sorted. Heap Sort exhibits an optimal worst-case time complexity of O(n log n).

Visualization

Complexity

Name	Best	Average	Worst	Memory	Stable	Comments
Heap sort	n log(n)	n log(n)	n log(n)	1	No

Code Example

def heap_sort(arr):
    def heapify(arr, n, i):
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2
        if left < n and arr[i] < arr[left]:
            largest = left
        if right < n and arr[largest] < arr[right]:
            largest = right
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            heapify(arr, n, largest)

    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)
    return arr

Radix Sort

Radix Sort is a non-comparative sorting algorithm that sorts numbers digit by digit, starting from the least significant digit to the most significant digit. It works by distributing the numbers into buckets based on each digit and repeatedly concatenating the buckets until the entire list is sorted. Radix Sort is particularly efficient for sorting integers.

Visualization

Complexity

Name	Best	Average	Worst	Memory	Stable	Comments
Radix sort	n * k	n * k	n * k	n + k	Yes	k - length of longest key

Code Example

def radix_sort(arr):
    max_value = max(arr)
    exp = 1
    while max_value // exp > 0:
        counting_sort(arr, exp)
        exp *= 10
    return arr

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    for i in range(n):
        index = arr[i] // exp
        count[index % 10] += 1
    for i in range(1, 10):
        count[i] += count[i - 1]
    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1
    for i in range(n):
        arr[i] = output[i]

Counting Sort

Counting Sort is an integer sorting algorithm that works by determining the number of occurrences of each distinct element in the input list. It then uses this information to compute the positions of each element in the sorted list. Counting Sort is efficient when the range of input values is small and known in advance.

Visualization

Complexity

Name	Best	Average	Worst	Memory	Stable	Comments
Counting sort	n + r	n + r	n + r	n + r	Yes	r - biggest number in array

Code Example

def counting_sort(arr):
    max_value = max(arr)
    count = [0] * (max_value + 1)
    for num in arr:
        count[num] += 1
    sorted_arr = []
    for i in range(len(count)):
        sorted_arr.extend([i] * count[i])
    return sorted_arr

Comparison and Summary

In summary, sorting algorithms come in various flavors, each with its strengths and weaknesses. Bubble Sort, Selection Sort, and Insertion Sort are simple to understand but may not be ideal for large datasets. Merge Sort, Quick Sort, and Heap Sort offer better performance and are suitable for a wide range of scenarios. Radix Sort and Counting Sort are specialized algorithms for sorting integers.

It's crucial to analyze the requirements and characteristics of your dataset to choose the most appropriate sorting algorithm. While our examples focused on Python, these algorithms can be implemented in other programming languages as well.

Remember, understanding sorting algorithms is an essential skill for any software engineer. By familiarizing yourself with different techniques and their trade-offs, you can optimize your code and provide efficient solutions to sorting challenges.

I hope this comprehensive guide has provided you with valuable insights into sorting algorithms. Happy sorting!