Sorting Algorithms (Basics)

# CHAPTER 26

Sorting Algorithms (Basics) #

1. Introduction #

2. Learning Objectives #

• Explain why "Nested Loops" inherently create O(n²) Time Complexity.

• Trace the physical array swaps of Bubble Sort.

• Understand the Min-Finding logic of Selection Sort.

• Understand the Shifting logic of Insertion Sort.

• Identify scenarios where O(n²) sorting is acceptable.

3. Bubble Sort (The Simplest Algorithm) #

The Mechanics: Array: [5, 1, 4, 2, 8]

1. 1. Compare 5 and 1. (5 > 1). Swap them! -> [1, 5, 4, 2, 8]

1. 2. Compare 5 and 4. (5 > 4). Swap them! -> [1, 4, 5, 2, 8]

1. 3. Compare 5 and 2. Swap! -> [1, 4, 2, 5, 8]

1. 4. Compare 5 and 8. (5 < 8). No swap.

// Java Example: Optimized Bubble Sort
public void bubbleSort(int[] arr) {
    int n = arr.length;
    boolean swapped;
    
    // Outer loop controls how many passes we do
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        
        // Inner loop pushes the largest remaining number to the right
        // We subtract 'i' because the last 'i' elements are already sorted!
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap logic
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        // If we did a full pass with 0 swaps, the array is perfectly sorted!
        if (!swapped) break;
    }
}

4. Selection Sort (The Minimizer) #

The Mechanics: Array: [5, 1, 4, 2, 8]

1. 1. Scan the whole array. The lowest number is 1.

1. 2. Swap 1 with the number in the first slot (5). -> [1, 5, 4, 2, 8]

1. 3. The slot [0] is now permanently sorted. Move to slot [1].

1. 4. Scan the remaining array [5, 4, 2, 8]. The lowest is 2.

1. 5. Swap 2 with the number in the current slot (5). -> [1, 2, 4, 5, 8]

# Python Example: Selection Sort
def selection_sort(arr):
    n = len(arr)
    
    for i in range(n):
        min_idx = i # Assume the current slot is the lowest
        
        # Scan the rest of the array to prove it
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j # Found a new lowest!
                
        # Swap the lowest number to the front of the unsorted boundary
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

5. Insertion Sort (The Card Player) #

The Mechanics: Array: [5, 1, 4, 2, 8]

1. 1. 5 is the first card. It's sorted.

1. 2. Pick up 1. Compare to 5. Shift 5 to the right, insert 1. -> [1, 5, 4, 2, 8]

1. 3. Pick up 4. Compare to 5. Shift 5 right, insert 4. -> [1, 4, 5, 2, 8]

// C++ Example: Insertion Sort
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i]; // The card we picked up
        int j = i - 1;

        // Shift elements to the right to make a gap for the key
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key; // Drop the card into the gap
    }
}

6. Complexity Analysis (The Tragedy of Nested Loops) #

7. Real-World Applications #

1. 1. Tiny Datasets: If an array only has 10 elements, O(n²) is literally 100 CPU instructions (completed in 0.000001 seconds). Setting up the massive recursive memory overhead of advanced algorithms (like Merge Sort) is actually *slower* for tiny arrays!

1. 2. Nearly Sorted Data: If an array is already mostly sorted, Insertion Sort detects this and skips the inner loop, achieving blistering fast O(n) linear execution speeds! Modern Python uses Timsort, which actively switches to Insertion Sort for tiny, pre-sorted chunks.

8. Common Mistakes #

• Forgetting the Optimization Boolean: When writing Bubble Sort in an interview, you MUST include the boolean swapped flag. If the array becomes fully sorted early on pass 2, the algorithm should abort. If you don't include the flag, the algorithm will mindlessly loop hundreds of times over already sorted data.

9. Exercises #

1. 1. Trace the exact array sequence if you execute Selection Sort on [9, 2, 5, 1].

1. 2. Why does Selection Sort always execute in O(n²) time, even if the array is already perfectly sorted?

10. MCQs with Answers #

11. Interview Preparation #

• *Conceptual:* "Debate the practical execution differences between Bubble Sort and Insertion Sort on an array that is 99% sorted, but possesses one single misaligned number at the very end of the array." *(Answer: Both will execute in O(n) time! Bubble sort will bubble it left over one pass. Insertion sort will shift the array exactly once).*

12. FAQs #

13. Summary #

14. Next Chapter Recommendation #