Essential Sorting Algorithms Explained: Bubble, Selection, Insertion

Understanding Sorting Algorithms

Sorting algorithms organize data in ascending or descending order—a fundamental skill for coding interviews. While not used in competitive programming, interviewers frequently test understanding of basic sorts like bubble, selection, and insertion sort. These O(n²) algorithms build foundational knowledge before tackling efficient sorts like merge or quick sort (O(n log n)).

How Sorting Works

Sorting rearranges elements systematically. Consider [4, 1, 5, 2, 3]:

• Ascending order: [1, 2, 3, 4, 5]
• Descending order: [5, 4, 3, 2, 1]

Bubble Sort: Moving Largest Elements to End

Bubble sort compares adjacent elements repeatedly, pushing larger values toward the end through swaps. Analysis shows it requires n-1 passes for n elements.

Step-by-Step Process

1. Pass 1: Compare adjacent pairs left-to-right:
   • Swap 4 and 1 → [1, 4, 5, 2, 3]
   • Swap 5 and 2 → [1, 4, 2, 5, 3]
   • Swap 5 and 3 → [1, 4, 2, 3, 5] (5 sorted)
2. Pass 2: Repeat for unsorted portion [1, 4, 2, 3]:
   • Swap 4 and 2 → [1, 2, 4, 3, 5]
   • Swap 4 and 3 → [1, 2, 3, 4, 5] (4 and 5 sorted)
3. Early termination: If no swaps occur, the array is sorted.

Optimization: Use a swapped flag to skip unnecessary passes.

Implementation and Complexity

void bubbleSort(int arr[], int n) {
  for (int i = 0; i < n-1; i++) {
    bool swapped = false;
    for (int j = 0; j < n-i-1; j++) {
      if (arr[j] > arr[j+1]) { // For descending: arr[j] < arr[j+1]
        swap(arr[j], arr[j+1]);
        swapped = true;
      }
    }
    if (!swapped) break; // Early exit if sorted
  }
}

Time Complexity: O(n²) worst/average case.

Selection Sort: Building Sorted Portion from Start

Selection sort divides the array into sorted and unsorted regions, selecting the smallest element from the unsorted section and swapping it to the front.

Execution Workflow

1. Pass 1: Find min in [4,1,5,2,3] → 1. Swap with index 0: [1,4,5,2,3]
2. Pass 2: Find min in [4,5,2,3] → 2. Swap with index 1: [1,2,5,4,3]
3. Pass 3: Find min in [5,4,3] → 3. Swap with index 2: [1,2,3,4,5]

Code and Performance

void selectionSort(int arr[], int n) {
  for (int i = 0; i < n-1; i++) {
    int minIdx = i;
    for (int j = i+1; j < n; j++) {
      if (arr[j] < arr[minIdx]) // For descending: arr[j] > arr[minIdx]
        minIdx = j;
    }
    swap(arr[i], arr[minIdx]);
  }
}

Time Complexity: O(n²) always due to nested loops.

Insertion Sort: Inserting Elements into Sorted Segment

Insertion sort builds a sorted subarray by inserting one element at a time into its correct position, similar to arranging playing cards.

Dry Run Example

1. Start: [4,1,5,2,3]
   • Sorted: [4], Unsorted: [1,5,2,3]
   • Insert 1 → [1,4,5,2,3]
2. Sorted: [1,4], Unsorted: [5,2,3]
   • Insert 5 → [1,4,5,2,3]
3. Sorted: [1,4,5], Unsorted: [2,3]
   • Insert 2 → Shift 5 and 4 → [1,2,4,5,3]

Implementation Details

void insertionSort(int arr[], int n) {
  for (int i = 1; i < n; i++) {
    int current = arr[i];
    int j = i-1;
    while (j >= 0 && arr[j] > current) { // For descending: arr[j] < current
      arr[j+1] = arr[j]; // Shift elements
      j--;
    }
    arr[j+1] = current; // Insert element
  }
}

Time Complexity: O(n²) worst-case, O(n) best-case for pre-sorted arrays.

Key Comparisons and Takeaways

Algorithm	Best Case	Worst Case	In-Place	Stable	Use Case
Bubble Sort	O(n)	O(n²)	Yes	Yes	Educational purposes
Selection Sort	O(n²)	O(n²)	Yes	No	Small datasets
Insertion Sort	O(n)	O(n²)	Yes	Yes	Partially sorted data

Actionable Checklist

1. Dry-run each algorithm on [4,1,5,2,3] for descending order.
2. Implement all three in your preferred language.
3. Compare performance using arrays of size 10, 100, and 1000.

Pro Tip: Practice identifying off-by-one errors in loop conditions—a common interview pitfall.

"Understanding these sorts unlocks advanced algorithms. Master the swaps, comparisons, and edge cases."

Which algorithm's optimization potential do you find most intriguing? Share your experiments below!

---

References:

1. Cormen, T. H. Introduction to Algorithms (Sorting Foundations)
2. MIT OpenCourseware: Algorithmic Complexity (2023 Analysis)