Sorting Algorithms

Learning Objectives

• Understand why sorting is required.
• Compare common sorting techniques.
• Choose a suitable algorithm by input size.

Why Sorting Matters

Sorted data improves readability, search speed, ranking, and report generation.

Core Algorithms

• Bubble Sort: simple, educational, O(n^2).
• Selection Sort: fewer swaps, still O(n^2).
• Insertion Sort: good for small/nearly-sorted data.
• Merge/Quick Sort: better for large datasets.

Complexity Snapshot

• Bubble/Selection/Insertion: O(n^2)
• Merge Sort: O(n log n)
• Quick Sort: average O(n log n), worst O(n^2)

Practical Example

Marks [67, 82, 45, 91] sorted ascending become [45, 67, 82, 91].

Practice Tasks

1. Implement bubble sort with pass-by-pass output.
2. Count comparisons and swaps for selection sort.
3. Compare runtime for n=100 and n=1000.

Summary

Start with simple sorts for understanding, then move to O(n log n) for scale.