Project 2: Sorting Algorithm Showdown

Build a terminal sorting visualizer that compares classic sorting algorithms.

Quick Reference

Attribute Value
Difficulty Level 2: Intermediate
Time Estimate 1-2 weeks
Language C (Alternatives: Rust, Python, Go)
Prerequisites Project 1, arrays, pointers, recursion basics
Key Topics Sorting, divide and conquer, stability, in-place algorithms

1. Learning Objectives

By completing this project, you will:

  1. Implement at least eight sorting algorithms from scratch.
  2. Explain stability and in-place trade-offs.
  3. Visualize algorithm behavior step by step.
  4. Compare empirical performance with theoretical bounds.

2. Theoretical Foundation

2.1 Core Concepts

  • Comparison vs non-comparison sorts: Comparison sorts are bounded by O(n log n); counting and radix break the bound.
  • Stability: Preserving relative order of equal elements matters for multi-key sorts.
  • Partitioning: Quicksort relies on partitioning around a pivot.
  • Heap invariant: Heap sort depends on maintaining a max-heap in an array.

2.2 Why This Matters

Sorting is the foundation of many other algorithms. Understanding different strategies helps you choose the right approach for data size, memory constraints, and stability needs.

2.3 Historical Context / Background

Quicksort (Hoare, 1960s) and mergesort (von Neumann, 1940s) reflect two different strategies: in-place partitioning vs stable merging.

2.4 Common Misconceptions

  • Misconception: Quicksort is always fastest. Reality: Worst-case is O(n^2) without careful pivot selection.
  • Misconception: Counting sort is always better. Reality: It depends on key range size.

3. Project Specification

3.1 What You Will Build

A terminal visualization that displays bars (or characters) moving as different sorts operate, plus a benchmark mode that compares total time and operations.

3.2 Functional Requirements

  1. Sorting suite: Bubble, selection, insertion, merge, quick, heap, counting, radix.
  2. Visualization mode: Step-by-step swaps or passes with adjustable speed.
  3. Benchmark mode: Run on multiple sizes and record metrics.
  4. Result report: Summary of time, comparisons, swaps.

3.3 Non-Functional Requirements

  • Performance: Visualization should not distort benchmark mode.
  • Reliability: Sorting must be correct for all input sizes.
  • Usability: Clear CLI flags for mode, algorithm, size.

3.4 Example Usage / Output

$ ./sort-showdown --algo quick --size 50 --visual
[|||||      ] swap 12 and 23
...
$ ./sort-showdown --benchmark --sizes 100,1000,5000
Algorithm  Time(ms)  Comparisons  Swaps
Quick      12        12034        3500
Merge      15        9800         0

3.5 Real World Outcome

Run ./sort-showdown --visual --algo merge. You will see chunks merging into sorted order. Then run the benchmark mode to see quicksort dominate average cases while mergesort stays stable and predictable.

4. Solution Architecture

4.1 High-Level Design

┌───────────────┐     ┌─────────────┐     ┌──────────────┐
│ Input Builder │────▶│ Sort Engine │────▶│ Metrics Store │
└───────────────┘     └─────┬───────┘     └─────┬────────┘
                            │                 │
                      ┌─────▼─────┐     ┌──────▼──────┐
                      │ Visualizer│     │ Reporter    │
                      └───────────┘     └─────────────┘

4.2 Key Components

Component Responsibility Key Decisions
Sort Engine Implement algorithms Consistent comparison callbacks
Visualizer Render swaps/passes Decouple from benchmark mode
Metrics Count comparisons/swaps Per-algorithm counters

4.3 Data Structures

struct Metrics {
    long comparisons;
    long swaps;
    double ms;
};

4.4 Algorithm Overview

Key Algorithm: Quicksort (Average O(n log n))

  1. Choose a pivot.
  2. Partition array into less/greater.
  3. Recurse on subarrays.

Complexity Analysis:

  • Time: O(n log n) average, O(n^2) worst
  • Space: O(log n) recursion stack

5. Implementation Guide

5.1 Development Environment Setup

cc -O2 -Wall -o sort-showdown src/*.c

5.2 Project Structure

sort-showdown/
├── src/
│   ├── main.c
│   ├── sorts.c
│   ├── sorts.h
│   ├── metrics.c
│   ├── viz.c
├── tests/
└── README.md

5.3 The Core Question You’re Answering

“How do different sorting strategies behave, and what does that behavior look like?”

5.4 Concepts You Must Understand First

Stop and research these before coding:

  1. Partitioning (quicksort)
  2. Stable vs unstable sorting
  3. Heap property and heapify

5.5 Questions to Guide Your Design

  1. How will you visualize a swap without slowing benchmarks?
  2. How will you represent array state in the terminal?
  3. How will you make counting and radix optional?

5.6 Thinking Exercise

Trace insertion sort on [5, 2, 4, 6, 1, 3] and write the array after each pass.

5.7 The Interview Questions They’ll Ask

  1. Why is merge sort stable but quicksort is not by default?
  2. What is the lower bound for comparison sorting?
  3. When is counting sort appropriate?

5.8 Hints in Layers

Hint 1: Implement a swap wrapper Count swaps inside a single function used by all algorithms.

Hint 2: Separate modes Disable visualization in benchmark mode.

Hint 3: Fixed pivot Start with last-element pivot, then add median-of-three.

5.9 Books That Will Help

Topic Book Chapter
Sorting overview “Algorithms, Fourth Edition” Ch. 2
Quicksort “Introduction to Algorithms” Ch. 7
Heaps “Introduction to Algorithms” Ch. 6

5.10 Implementation Phases

Phase 1: Foundation (3-4 days)

Goals:

  • Implement bubble, insertion, selection
  • Add metrics counters

Tasks:

  1. Write comparison and swap helpers.
  2. Add CLI for algorithm selection.

Checkpoint: Correct sorting for small arrays with metrics.

Phase 2: Core Functionality (4-5 days)

Goals:

  • Implement merge, quick, heap
  • Add visualization mode

Tasks:

  1. Add merge sort with temp buffer.
  2. Add quicksort with partition.

Checkpoint: Visualization renders for each algorithm.

Phase 3: Extensions (3-4 days)

Goals:

  • Add counting and radix sorts
  • Add benchmark report

Tasks:

  1. Implement counting with range detection.
  2. Output summary table.

Checkpoint: Benchmark mode prints results for all algorithms.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Visualization ncurses, ANSI ANSI bars Lightweight
Quicksort pivot last, random, median-of-three median-of-three Better worst-case
Counting sort fixed range, inferred range inferred More flexible

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Unit Tests Validate each sort Small fixed arrays
Integration Tests CLI modes Visual vs benchmark
Edge Case Tests Duplicates, sorted, reverse Stability checks

6.2 Critical Test Cases

  1. Sorted array remains unchanged.
  2. Reverse array is fully sorted.
  3. Duplicate-heavy arrays remain sorted and stable where expected.

6.3 Test Data

[3, 1, 2, 2, 5]
[5, 4, 3, 2, 1]
[1, 2, 3, 4, 5]

7. Common Pitfalls and Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
Incorrect partition loop Quicksort fails on duplicates Verify pivot handling
Off-by-one in heapify Heap sort breaks Check child index math
Visual mode timing Flickering output Add fixed delay

7.2 Debugging Strategies

  • Add asserts for array order after each pass.
  • Print intermediate arrays for small input sizes.

7.3 Performance Traps

Repeated screen clears in visualization can slow tests; disable for benchmarks.

8. Extensions and Challenges

8.1 Beginner Extensions

  • Add a speed slider for visualization.
  • Add a “shuffle and repeat” mode.

8.2 Intermediate Extensions

  • Add introsort (quicksort + heap fallback).
  • Measure cache misses with perf.

8.3 Advanced Extensions

  • Implement external merge sort for large files.
  • Add parallel merge sort.

9. Real-World Connections

9.1 Industry Applications

  • Sorting logs and analytics data at scale.
  • Preparing data for binary search and indexing.
  • musl qsort: Real-world C standard library implementation.
  • timsort: Python and Java standard sort.

9.3 Interview Relevance

  • Sorting algorithm trade-offs are common interview questions.
  • Stability and complexity are frequent discussion topics.

10. Resources

10.1 Essential Reading

  • “Algorithms, Fourth Edition” by Sedgewick - Ch. 2
  • “Introduction to Algorithms” (CLRS) - Ch. 6-7

10.2 Video Resources

  • Visual sort animations (search: “sorting algorithm visualization”)

10.3 Tools and Documentation

  • ncurses: https://invisible-island.net/ncurses/

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain why comparison sorts are lower-bounded by O(n log n).
  • I can describe how quicksort partitions an array.
  • I can explain stability and why it matters.

11.2 Implementation

  • All algorithms sort correctly.
  • Metrics are consistent across algorithms.
  • Visualization mode is optional and stable.

11.3 Growth

  • I can choose a sort based on constraints.
  • I can explain why counting sort can beat O(n log n).

12. Submission / Completion Criteria

Minimum Viable Completion:

  • At least five sorts implemented
  • Visual mode for at least two algorithms
  • Benchmark summary output

Full Completion:

  • Eight or more sorts
  • Stability notes in documentation

Excellence (Going Above and Beyond):

  • Introsort or external merge sort
  • Performance profiling report

This guide was generated from LEARN_ALGORITHMS_DEEP_DIVE.md. For the complete learning path, see the parent directory.