🧮 Sorting Algorithms: Concepts, Comparisons, and Curiosities

🧮 Sorting Algorithms: Concepts, Comparisons, and Curiosities#

📚 Overview of Common Sorting Algorithms#

Algorithm

Description

Time Complexity (Best/Average/Worst)

Stable?

Bubble Sort

Repeatedly swaps adjacent elements if they’re in the wrong order.

O(n) / O(n²) / O(n²)

✅ Yes

Insertion Sort

Builds the sorted list one item at a time by inserting into correct position.

O(n) / O(n²) / O(n²)

✅ Yes

Merge Sort

Divides array into halves, sorts recursively, and merges.

O(n log n) / O(n log n) / O(n log n)

✅ Yes

Quick Sort

Picks a pivot, partitions array, and sorts recursively.

O(n log n) / O(n log n) / O(n²)

❌ No

Timsort

Hybrid of merge and insertion sort (used in Python’s sorted()).

O(n) / O(n log n) / O(n log n)

✅ Yes

🧠 Conceptual Questions#

  1. Why is stability important in sorting?
    Hint: Think about sorting records with multiple fields.

  2. What makes Quick Sort faster in practice despite its worst-case time?

  3. How does Merge Sort guarantee performance regardless of input order?

  4. Why is Bubble Sort rarely used in real-world applications?

  5. What kind of data would make Insertion Sort outperform Quick Sort?

📝 Mini Quiz#

Question 1:
Which sorting algorithm is guaranteed to run in O(n log n) time regardless of input?

  • A) Bubble Sort

  • B) Merge Sort

  • C) Quick Sort

  • D) Insertion Sort
    ✅ Correct Answer: B

Question 2:
Which algorithm is most efficient for nearly sorted data?

  • A) Merge Sort

  • B) Bubble Sort

  • C) Insertion Sort

  • D) Quick Sort
    ✅ Correct Answer: C

Question 3:
Which sorting algorithm is used internally by Python’s sorted() function?

  • A) Merge Sort

  • B) Quick Sort

  • C) Timsort

  • D) Heap Sort
    ✅ Correct Answer: C

🎉 Fun Facts About Sorting#

  • 🧠 Timsort was invented by Tim Peters for Python and is also used in Java!

  • 🐢 Bubble Sort is often taught first because it’s conceptually simple—but it’s one of the slowest.

  • 🧩 Sorting networks are used in hardware implementations for parallel sorting.

  • 🧪 Radix Sort and Counting Sort can beat comparison-based sorts for integers.

  • 📈 Sorting is foundational—many algorithms (like searching, clustering, and graph traversal) rely on sorted data.

🔍 Reflection Prompt#

Think about a real-world scenario (e.g., sorting patient records, ranking sports teams, organizing emails).
Which sorting algorithm would you choose and why? Consider stability, speed, and input characteristics.

import time
import numpy as np
import matplotlib.pyplot as plt
import ipywidgets as widgets
from IPython.display import display, Markdown

# 🧬 Generate synthetic data
def generate_data(size=1000, seed=42):
    np.random.seed(seed)
    return np.random.randint(0, 10000, size).tolist()

# 🧮 Sorting algorithms
def bubble_sort(arr):
    a = arr.copy()
    for i in range(len(a)):
        for j in range(len(a)-1-i):
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]
    return a

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

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

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

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    less = [x for x in arr[1:] if x <= pivot]
    greater = [x for x in arr[1:] if x > pivot]
    return quick_sort(less) + [pivot] + quick_sort(greater)

# 🧠 Algorithm dictionary
algorithms = {
    "Bubble Sort": bubble_sort,
    "Insertion Sort": insertion_sort,
    "Merge Sort": merge_sort,
    "Quick Sort": quick_sort,
    "Built-in sorted()": sorted
}

# 🎛️ Widgets
size_slider = widgets.IntSlider(value=1000, min=10, max=5000, step=100, description="Data Size:")
dropdown = widgets.Dropdown(options=list(algorithms.keys()), value="Bubble Sort", description="Choose Algorithm:")
run_button = widgets.Button(description="Run Sort", button_style='success')
compare_button = widgets.Button(description="Compare All", button_style='info')
output = widgets.Output()

# 🧪 Single algorithm execution
def on_run_click(b):
    output.clear_output()
    data = generate_data(size_slider.value)
    algo_name = dropdown.value
    func = algorithms[algo_name]
    start = time.time()
    result = func(data)
    duration = time.time() - start
    with output:
        display(Markdown(f"### 🔍 {algo_name} Result"))
        print(f"Data Size: {len(data)}")
        print(f"Execution Time: {duration:.6f} seconds")

# 📈 Compare all algorithms
def on_compare_click(b):
    output.clear_output()
    data = generate_data(size_slider.value)
    times = {}
    for name, func in algorithms.items():
        start = time.time()
        func(data)
        times[name] = time.time() - start
    with output:
        display(Markdown("### 📊 Sorting Algorithm Performance Comparison"))
        plt.figure(figsize=(8, 5))
        plt.bar(times.keys(), times.values(), color='skyblue')
        plt.ylabel("Execution Time (seconds)")
        plt.xticks(rotation=45)
        plt.grid(True, linestyle='--', alpha=0.5)
        plt.tight_layout()
        plt.show()

run_button.on_click(on_run_click)
compare_button.on_click(on_compare_click)

# 🚀 Display UI
display(size_slider, dropdown, run_button, compare_button, output)
Contents