Example

In the previous article, we explored the fundamentals and practical applications of algorithms, learning that algorithms are effective tools for solving problems. In this article, we focus on sorting algorithms—delving into how they work and where they are applied. Sorting algorithms constitute a critically important category within algorithm design, as many real-world problems require data to be ordered, and the resulting sorted output is often essential for subsequent searching and processing tasks.

What Is a Sorting Algorithm?

A sorting algorithm is a method for arranging elements in a specific order—typically according to a defined comparison relationship. Common sorting algorithms include:

• Bubble Sort
• Selection Sort
• Insertion Sort
• Merge Sort
• Quick Sort
• Heap Sort

Different sorting algorithms vary significantly in performance, stability, and suitability for particular use cases; thus, selecting the appropriate sorting algorithm is crucial.

Introduction to Common Sorting Algorithms

1. Bubble Sort

Bubble sort is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares adjacent elements, and swaps them if they are in the wrong order.

Time Complexity: $O(n^2)$ in the worst case
Space Complexity: $O(1)$

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

# Example
data = [64, 34, 25, 12, 22, 11, 90]
sorted_data = bubble_sort(data)
print(sorted_data)  # Output: [11, 12, 22, 25, 34, 64, 90]

2. Selection Sort

Selection sort is a simple and intuitive sorting algorithm. Its core idea is to repeatedly find the minimum element from the unsorted portion and place it at the end of the sorted portion.

Time Complexity: $O(n^2)$ in the worst case
Space Complexity: $O(1)$

Code Example:

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

# Example
data = [64, 25, 12, 22, 11]
sorted_data = selection_sort(data)
print(sorted_data)  # Output: [11, 12, 22, 25, 64]

3. Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time by inserting each new element into its correct position within an already-sorted subsequence. It performs well on small datasets or nearly sorted data.

Time Complexity: $O(n^2)$ in the worst case; $O(n)$ in the best case
Space Complexity: $O(1)$

Code Example:

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

# Example
data = [12, 11, 13, 5, 6]
sorted_data = insertion_sort(data)
print(sorted_data)  # Output: [5, 6, 11, 12, 13]

4. Merge Sort

Merge sort is an efficient divide-and-conquer algorithm. It recursively divides an array into two halves, sorts each half independently, and then merges the sorted halves back together.

Time Complexity: $O(n \log n)$ in both worst and average cases
Space Complexity: $O(n)$

Code Example:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # Find midpoint
        L = arr[:mid]        # Split into left and right halves
        R = arr[mid:]

        merge_sort(L)        # Recursively sort left half
        merge_sort(R)        # Recursively sort right half

        i = j = k = 0

        # Merge L and R
        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
    return arr

# Example
data = [38, 27, 43, 3, 9, 82, 10]
sorted_data = merge_sort(data)
print(sorted_data)  # Output: [3, 9, 10, 27, 38, 43, 82]

5. Quick Sort

Quick sort is a highly efficient divide-and-conquer sorting algorithm. It selects a “pivot” element and partitions the array into two subarrays—one containing elements less than the pivot and the other containing elements greater than the pivot—then recursively sorts both subarrays.

Time Complexity: $O(n^2)$ in the worst case; $O(n \log n)$ in the best case
Space Complexity: $O(\log n)$

Code Example:

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]  # Choose pivot
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

# Example
data = [10, 7, 8, 9, 1, 5]
sorted_data = quick_sort(data)
print(sorted_data)  # Output: [1, 5, 7, 8, 9, 10]

6. Heap Sort

Heap sort is a comparison-based sorting algorithm that leverages the heap data structure—a complete binary tree satisfying the heap property—to sort data.