Sorting Algorithms: Bubble, Selection, Insertion, Merge, Quick, and Radix

TAKEAWAYS:

• Sorting algorithms rearrange data in ascending or descending order using comparisons and swaps.
• Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
• Merge Sort divides the array into halves, recursively sorts them, and merges the sorted halves.
• Quick Sort selects a pivot, partitions the array around the pivot, and recursively sorts the subarrays.
• Radix Sort sorts numbers digit by digit from least significant to most significant.
• Time complexity varies: O(n²) for Bubble/Selection/Insertion, O(n log n) for Merge/Quick, and O(nk) for Radix (where k is the number of digits).

1. Introduction to Sorting Algorithms

Sorting is the process of arranging elements in a specific order (ascending or descending). It is a fundamental operation in computer science with applications in databases, search engines, and financial systems.

Why Sort?

• Efficient searching (e.g., binary search requires sorted data).
• Data organization (e.g., sorting customer records by name).
• Algorithmic efficiency (e.g., many algorithms assume sorted input).

2. Classification of Sorting Algorithms

Sorting algorithms can be classified based on:

• Comparison-based: Compare elements to determine order (e.g., Bubble, Quick).
• Non-comparison-based: Use properties of data (e.g., Radix, Counting).
• In-place: Require minimal extra space (e.g., Bubble, Selection).
• Out-of-place: Require additional space (e.g., Merge).

3. Bubble Sort

Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process repeats until the list is sorted.

How It Works

1. Compare adjacent elements.
2. Swap if they are in the wrong order.
3. Repeat for each element until no more swaps are needed.

Algorithm Steps

flowchart TD
    A["Start with unsorted array"] --> B["i = 0"]
    B --> C["j = 0"]
    C --> D["Compare arr[j] and arr[j+1]"]
    D --> E["If arr[j] > arr[j+1], swap them"]
    E --> F["j = j + 1"]
    F --> G["If j < n-1-i, go to D"]
    G --> H["i = i + 1"]
    H --> I["If i < n-1, go to B"]
    I --> J["Array is sorted"]

Time Complexity

• Best Case: O(n) (already sorted).
• Average/Worst Case: O(n²).

Space Complexity: O(1) (in-place).

Example

Input: [5, 3, 8, 4, 2] Pass 1: [3, 5, 4, 2, 8] (swaps: 5↔3, 8↔4, 4↔2) Pass 2: [3, 4, 2, 5, 8] (swaps: 5↔4, 4↔2) Pass 3: [3, 2, 4, 5, 8] (swap: 4↔2) Pass 4: [2, 3, 4, 5, 8] (no swaps, sorted).

Visualization

Initial: [5, 3, 8, 4, 2]
After Pass 1: [3, 5, 4, 2, 8]
After Pass 2: [3, 4, 2, 5, 8]
After Pass 3: [2, 3, 4, 5, 8]

Advantages

• Simple to implement.
• No extra memory needed.

Disadvantages

• Inefficient for large datasets (O(n²) time).
• Poor cache performance.

4. Selection Sort

Selection Sort divides the array into a sorted and unsorted part. It repeatedly selects the smallest element from the unsorted part and swaps it with the first unsorted element.

How It Works

1. Find the minimum element in the unsorted part.
2. Swap it with the first unsorted element.
3. Repeat until the entire array is sorted.

Algorithm Steps

flowchart TD
    A["Start with unsorted array"] --> B["i = 0"]
    B --> C["min_idx = i"]
    C --> D["j = i + 1"]
    D --> E["If arr[j] < arr[min_idx], min_idx = j"]
    E --> F["j = j + 1"]
    F --> G["If j < n, go to D"]
    G --> H["Swap arr[i] and arr[min_idx]"]
    H --> I["i = i + 1"]
    I --> J["If i < n-1, go to B"]
    J --> K["Array is sorted"]

Time Complexity

• Best/Average/Worst Case: O(n²).

Space Complexity: O(1) (in-place).

Example

Input: [64, 25, 12, 22, 11] Pass 1: Swap 64 and 11 → [11, 25, 12, 22, 64] Pass 2: Swap 25 and 12 → [11, 12, 25, 22, 64] Pass 3: No swap needed (22 is already in place). Pass 4: Swap 25 and 22 → [11, 12, 22, 25, 64] Final: [11, 12, 22, 25, 64]

Visualization

Initial: [64, 25, 12, 22, 11]
After Pass 1: [11, 25, 12, 22, 64]
After Pass 2: [11, 12, 25, 22, 64]
After Pass 3: [11, 12, 22, 25, 64]

Advantages

• Minimizes swaps (O(n) swaps).
• Simple to implement.

Disadvantages

• Inefficient for large datasets (O(n²) time).
• Poor cache performance.

5. Insertion Sort

Insertion Sort builds the sorted array one element at a time. It takes each element and inserts it into its correct position in the sorted part.

How It Works

1. Start with the second element.
2. Compare it with the elements in the sorted part.
3. Insert it into the correct position.

Algorithm Steps

flowchart TD
    A["Start with unsorted array"] --> B["i = 1"]
    B --> C["key = arr[i]"]
    C --> D["j = i - 1"]
    D --> E["If arr[j] > key, shift arr[j+1] = arr[j]"]
    E --> F["j = j - 1"]
    F --> G["If j >= 0 and arr[j] > key, go to E"]
    G --> H["Insert key after arr[j+1]"]
    H --> I["i = i + 1"]
    I --> J["If i < n, go to B"]
    J --> K["Array is sorted"]

Time Complexity

• Best Case: O(n) (already sorted).
• Average/Worst Case: O(n²).

Space Complexity: O(1) (in-place).

Example

Input: [12, 11, 13, 5, 6] Pass 1: Insert 11 before 12 → [11, 12, 13, 5, 6] Pass 2: Insert 13 after 12 → [11, 12, 13, 5, 6] Pass 3: Insert 5 before 11 → [5, 11, 12, 13, 6] Pass 4: Insert 6 between 12 and 13 → [5, 6, 11, 12, 13] Final: [5, 6, 11, 12, 13]

Visualization

Initial: [12, 11, 13, 5, 6]
After Pass 1: [11, 12, 13, 5, 6]
After Pass 2: [11, 12, 13, 5, 6]
After Pass 3: [5, 11, 12, 13, 6]
After Pass 4: [5, 6, 11, 12, 13]

Advantages

• Efficient for small or nearly sorted datasets.
• Stable (preserves order of equal elements).

Disadvantages

• Inefficient for large datasets (O(n²) time).

6. Merge Sort

Merge Sort is a divide-and-conquer algorithm that divides the array into halves, recursively sorts them, and merges the sorted halves.

How It Works

1. Divide the array into two halves.
2. Recursively sort each half.
3. Merge the two sorted halves.

Algorithm Steps

flowchart TD
    A["Start with unsorted array"] --> B["Divide array into two halves"]
    B --> C["Recursively sort left half"]
    B --> D["Recursively sort right half"]
    C --> E["If left half has one element, return"]
    D --> F["If right half has one element, return"]
    E --> G["Merge left and right halves"]
    F --> G
    G --> H["Return merged sorted array"]

Time Complexity

• Best/Average/Worst Case: O(n log n).

Space Complexity: O(n) (requires auxiliary space).

Example

Input: [38, 27, 43, 3, 9, 82, 10] Divide: [38, 27, 43] and [3, 9, 82, 10] Recursively Sort:

• [38, 27, 43] → [27, 38, 43]
• [3, 9, 82, 10] → [3, 9, 10, 82] Merge: [27, 38, 43, 3, 9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]

Visualization

Initial: [38, 27, 43, 3, 9, 82, 10]
After Divide: [38, 27, 43] | [3, 9, 82, 10]
After Sort: [27, 38, 43] | [3, 9, 10, 82]
After Merge: [3, 9, 10, 27, 38, 43, 82]

Advantages

• Stable and efficient (O(n log n) time).
• Works well for linked lists.

Disadvantages

• Requires O(n) extra space.
• Slower for small datasets due to overhead.

7. Quick Sort

Quick Sort is another divide-and-conquer algorithm that selects a pivot, partitions the array around the pivot, and recursively sorts the subarrays.

How It Works

1. Choose a pivot (e.g., last element).
2. Partition the array so that elements less than the pivot are on the left, and greater elements are on the right.
3. Recursively sort the left and right partitions.

Algorithm Steps

flowchart TD
    A["Start with unsorted array"] --> B["Choose pivot (e.g., last element)"]
    B --> C["Partition array around pivot"]
    C --> D["Elements < pivot on left, > pivot on right"]
    D --> E["Recursively sort left partition"]
    D --> F["Recursively sort right partition"]
    E --> G["Return sorted array"]
    F --> G

Time Complexity

• Best/Average Case: O(n log n).
• Worst Case: O(n²) (if pivot is poorly chosen).

Space Complexity: O(log n) (due to recursion stack).

Example

Input: [10, 7, 8, 9, 1, 5] Pivot: 5 (last element) Partition: [1, 5] and [10, 7, 8, 9] Recursively Sort:

• [1, 5] is already sorted.
• [10, 7, 8, 9] → Pivot: 9 → [7, 8, 9, 10] Final: [1, 5, 7, 8, 9, 10]

Visualization

Initial: [10, 7, 8, 9, 1, 5]
After Partition: [1, 5] | [10, 7, 8, 9]
After Sort: [1, 5, 7, 8, 9, 10]

Advantages

• Fastest in practice (O(n log n) average case).
• In-place (minimal extra space).

Disadvantages

• Worst-case O(n²) if pivot is poorly chosen.
• Unstable (may not preserve order of equal elements).

8. Radix Sort

Radix Sort sorts numbers digit by digit from the least significant digit (LSD) to the most significant digit (MSD). It uses a stable sorting algorithm (e.g., Counting Sort) as a subroutine.

How It Works

1. Sort numbers based on the least significant digit.
2. Repeat for each digit until the most significant digit is processed.

Algorithm Steps

flowchart TD
    A["Start with unsorted array"] --> B["Find the maximum number"]
    B --> C["Determine the number of digits (d)"]
    C --> D["For i from 0 to d-1"]
    D --> E["Sort numbers based on digit at position i (LSD to MSD)"]
    E --> F["Use Counting Sort for stability"]
    F --> G["Repeat until all digits are processed"]
    G --> H["Array is sorted"]

Time Complexity

• Best/Average/Worst Case: O(nk), where k is the number of digits.

Space Complexity: O(n + k).

Example

Input: [170, 45, 75, 90, 802, 24, 2, 66] Step 1 (LSD): Sort by units digit → [170, 45, 75, 90, 802, 24, 2, 66] → [2, 24, 66, 45, 75, 90, 170, 802] Step 2 (Tens digit): Sort by tens digit → [2, 24, 45, 66, 75, 802, 90, 170] Step 3 (Hundreds digit): Sort by hundreds digit → [2, 24, 45, 66, 75, 90, 170, 802] Final: [2, 24, 45, 66, 75, 90, 170, 802]

Visualization

Initial: [170, 45, 75, 90, 802, 24, 2, 66]
After LSD: [2, 24, 66, 45, 75, 90, 170, 802]
After Tens: [2, 24, 45, 66, 75, 802, 90, 170]
After Hundreds: [2, 24, 45, 66, 75, 90, 170, 802]

Advantages

• Linear time for fixed-digit numbers (O(n)).
• Stable.

Disadvantages

• Requires extra space.
• Not suitable for very large numbers.

9. Comparison of Sorting Algorithms

In the Real World

1. eSewa/Khalti (Payment Gateways)

   • Idea: Radix Sort is used to sort transaction IDs or amounts quickly, ensuring efficient processing of large volumes of payments.
   • How: Radix Sort’s O(nk) time complexity is ideal for sorting fixed-length strings (e.g., transaction IDs) or numbers with a limited digit range.

2. Daraz (E-commerce Platform)

   • Idea: Merge Sort is used to sort product listings by price or popularity.
   • How: When a user filters products by price, Merge Sort ensures the results are returned in O(n log n) time, improving user experience.

3. NEPSE (Nepal Stock Exchange)

   • Idea: Quick Sort is used to sort stock prices or trading volumes in real-time.
   • How: Quick Sort’s average-case O(n log n) performance allows NEPSE to handle high-frequency trading data efficiently.

4. Pathao (Ride-Hailing App)

   • Idea: Insertion Sort is used to sort nearby drivers by distance or availability.
   • How: When a user requests a ride, the app sorts nearby drivers in real-time using Insertion Sort, which is efficient for small, dynamic datasets.

5. Kathmandu Traffic Routes (Real-Life Example)

   • Scenario: Imagine sorting vehicles by registration number for a traffic check.
   • Algorithm: Radix Sort is used to sort the registration numbers (e.g., "KA-0123", "KA-4567") digit by digit.
   • Why: Radix Sort efficiently handles fixed-length strings (registration numbers) and ensures quick sorting even for large datasets.

Exam Tip

• Focus on Time Complexity: Always state the best, average, and worst-case time complexity for each algorithm. For example, Bubble Sort is O(n²) in all cases, while Merge Sort is O(n log n) in all cases.
• Visualize Steps: Draw the array after each step of sorting (e.g., after each pass in Bubble Sort or after each merge in Merge Sort). This helps in understanding the algorithm’s progression.
• Compare Algorithms: Know when to use which algorithm. For example:
  • Use Bubble/Selection/Insertion Sort for small datasets or nearly sorted data.
  • Use Merge/Quick Sort for large datasets due to their O(n log n) efficiency.
  • Use Radix Sort for sorting fixed-length strings or numbers.
• Stability Matters: Mention whether an algorithm is stable (e.g., Merge Sort, Insertion Sort) or unstable (e.g., Quick Sort, Selection Sort) when relevant.
• Practice Coding: Write code for at least one algorithm (e.g., Bubble Sort) and trace its execution step-by-step for a given input. This is often tested in exams.
• Real-World Tie-Ins: Relate sorting algorithms to real-world applications (e.g., sorting transaction IDs in eSewa or product listings in Daraz) to score extra marks in descriptive questions.