Sorting Algorithms - From Classic to Modern
Published: 2023-06-22 06:12:52

### 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
![Algorithm Visualization](https://upload.wikimedia.org/wikipedia/commons/c/c8/Bubble-sort-example-300px.gif)

#### Complexity
| Name                  | Best            | Average             | Worst               | Memory    | Stable    | Comments  |
| --------------------- | :-------------: | :-----------------: | :-----------------: | :-------: | :-------: | :-------- |
| **Bubble sort**       | n               | n<sup>2</sup>       | n<sup>2</sup>       | 1         | Yes       |           |

#### Code Example
```python
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
![Algorithm Visualization](https://upload.wikimedia.org/wikipedia/commons/b/b0/Selection_sort_animation.gif)

![Algorithm Visualization](https://upload.wikimedia.org/wikipedia/commons/9/94/Selection-Sort-Animation.gif)

#### Complexity
| Name                  | Best            | Average             | Worst               | Memory    | Stable    | Comments  |
| --------------------- | :-------------: | :-----------------: | :-----------------: | :-------: | :-------: | :-------- |
| **Selection sort**    | n<sup>2</sup>   | n<sup>2</sup>       | n<sup>2</sup>       | 1         | No        |           |

#### Code Example
```python
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
![Algorithm Visualization](https://upload.wikimedia.org/wikipedia/commons/4/42/Insertion_sort.gif)

![Algorithm Visualization](https://upload.wikimedia.org/wikipedia/commons/0/0f/Insertion-sort-example-300px.gif)

#### Complexity
| Name                  | Best            | Average             | Worst               | Memory    | Stable    | Comments  |
| --------------------- | :-------------: | :-----------------: | :-----------------: | :-------: | :-------: | :-------- |
| **Insertion sort**    | n               | n<sup>2</sup>       | n<sup>2</sup>       | 1         | Yes       |           |

#### Code Example
```python
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
![Merge Sort](https://upload.wikimedia.org/wikipedia/commons/c/cc/Merge-sort-example-300px.gif)

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).

![Merge Sort](https://upload.wikimedia.org/wikipedia/commons/e/e6/Merge_sort_algorithm_diagram.svg)

#### Complexity
| Name                  | Best            | Average             | Worst               | Memory    | Stable    | Comments  |
| --------------------- | :-------------: | :-----------------: | :-----------------: | :-------: | :-------: | :-------- |
| **Merge sort**        | n&nbsp;log(n)   | n&nbsp;log(n)       | n&nbsp;log(n)       | n         | Yes       |           |

#### Code Example
```python
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
![Quicksort](https://upload.wikimedia.org/wikipedia/commons/6/6a/Sorting_quicksort_anim.gif)

#### Complexity
| Name                  | Best            | Average             | Worst               | Memory    | Stable    | Comments  |
| --------------------- | :-------------: | :-----------------: | :-----------------: | :-------: | :-------: | :-------- |
| **Quick sort**        | n&nbsp;log(n)   | n&nbsp;log(n)       | n<sup>2</sup>       | log(n)    | No        |  Quicksort is usually done in-place with O(log(n)) stack space |

#### Code Example
```python
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
![Algorithm Visualization](https://upload.wikimedia.org/wikipedia/commons/1/1b/Sorting_heapsort_anim.gif)

![Algorithm Visualization](https://upload.wikimedia.org/wikipedia/commons/4/4d/Heapsort-example.gif)

#### Complexity
| Name                  | Best            | Average             | Worst               | Memory    | Stable    | Comments  |
| --------------------- | :-------------: | :-----------------: | :-----------------: | :-------: | :-------: | :-------- |
| **Heap sort**         | n&nbsp;log(n)   | n&nbsp;log(n)       | n&nbsp;log(n)       | 1         | No        |           |

#### Code Example
```python
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
![Radix Sort](https://i.makeagif.com/media/7-17-2016/hlfsiC.gif)

#### 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
```python
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
![Counting Sort](https://media.tenor.com/zswbYsLbYqEAAAAd/counting-sort.gif)

#### 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
```python
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!