Sorting Algos and Patterns - (Theory)

Sorting Algorithms - TC and SC (Concept)

This includes:

• Concept, dry run, time & space complexity of Bubble, Selection, and Insertion Sort

• Real-life analogy for each algorithm

• Scenarios and patterns where sorting is essential in problem-solving

• Java code for each sorting algorithm

• All 6 problem patterns explained with real coding examples

• Explanation of why inbuilt sort() is preferred

Introduction to Sorting

Sorting is the process of rearranging data in a specific order (typically ascending or descending). Sorting is fundamental in programming because many algorithms (binary search, interval merge, greedy strategies) depend on sorted data to function correctly.

1. Bubble Sort

Concept:

Repeatedly compares adjacent elements and swaps them if they are in the wrong order. After each pass, the largest unsorted element "bubbles up" to its correct position.

Dry Run:

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

• Pass 1:
  [3, 5, 1, 4, 2]
[3, 1, 5, 4, 2]
[3, 1, 4, 5, 2]
[3, 1, 4, 2, 5]

• Pass 2:
  [1, 3, 4, 2, 5]
[1, 3, 4, 2, 5]
[1, 3, 2, 4, 5]

• Pass 3:
  [1, 3, 2, 4, 5]
[1, 2, 3, 4, 5]

Done.

Time Complexity:

• Worst Case: O(n²)

• Best Case: O(n) (optimized with a swapped flag)

• Average: O(n²)

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

Real-life Analogy:

Like bubbles rising to the surface in a liquid — each biggest element rises to its correct place at the end.

Java Code:

void bubbleSort(int[] arr) {
    int n = arr.length;
    boolean swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

2. Selection Sort

Concept:

Finds the smallest element in the unsorted portion and places it in its correct position by swapping.

Dry Run:

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

• Pass 1: Smallest = 1 → Swap with 5 → [1, 3, 5, 4, 2]

• Pass 2: Smallest = 2 → Swap with 3 → [1, 2, 5, 4, 3]

• Pass 3: Smallest = 3 → Swap with 5 → [1, 2, 3, 4, 5]

Time Complexity:

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

Space Complexity: O(1)

Real-life Analogy:

Like choosing the best player in a draft from the remaining pool each time.

Java Code:

void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        int temp = arr[minIdx];
        arr[minIdx] = arr[i];
        arr[i] = temp;
    }
}

3. Insertion Sort

Concept:

Builds the sorted array by picking one element at a time and inserting it into the correct position in the already sorted portion.

Dry Run:

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

• Step 1: 3 < 5 → shift 5 → [3, 5, 1, 4, 2]

• Step 2: 1 < 5 → shift 5
  1 < 3 → shift 3 → [1, 3, 5, 4, 2]

• Continue until [1, 2, 3, 4, 5]

Time Complexity:

• Worst: O(n²)

• Best: O(n) (already sorted)

• Average: O(n²)

Space Complexity: O(1)

Real-life Analogy:

Like sorting playing cards in your hand.

Java Code:

void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Comparison Table

Why Inbuilt sort() Is More Effective

Java Arrays.sort():

• Primitives: Dual Pivot QuickSort (O(n log n))

• Objects: TimSort (Merge Sort + Insertion Sort hybrid)

Python sort():

• Uses TimSort

Benefits:

• Stable, adaptive, fast for both nearly sorted and random data.

• Efficient for large-scale real-world use cases.

Problem-Solving Scenarios (Patterns with Code)

1. Sort + Two Pointers

Problem: Find if two numbers sum to a target

boolean hasPairWithSum(int[] arr, int target) {
    Arrays.sort(arr);
    int i = 0, j = arr.length - 1;
    while (i < j) {
        int sum = arr[i] + arr[j];
        if (sum == target) return true;
        else if (sum < target) i++;
        else j--;
    }
    return false;
}

2. Sort + Binary Search

Problem: Check if target exists

boolean contains(int[] arr, int target) {
    Arrays.sort(arr);
    int l = 0, r = arr.length - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == target) return true;
        else if (arr[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return false;
}

3. Kth Smallest Element

Problem: Return the kth smallest element

int kthSmallest(int[] arr, int k) {
    Arrays.sort(arr);
    return arr[k - 1];
}

4. Greedy Algorithm

Problem: Activity selection (maximum non-overlapping meetings)

class Meeting {
    int start, end;
    Meeting(int s, int e) { start = s; end = e; }
}

int maxMeetings(List<Meeting> meetings) {
    meetings.sort((a, b) -> a.end - b.end);
    int count = 0, lastEnd = -1;
    for (Meeting m : meetings) {
        if (m.start > lastEnd) {
            count++;
            lastEnd = m.end;
        }
    }
    return count;
}

5. Interval Scheduling (Merge Intervals)

class Interval {
    int start, end;
    Interval(int s, int e) { start = s; end = e; }
}

List<Interval> merge(List<Interval> intervals) {
    intervals.sort((a, b) -> a.start - b.start);
    List<Interval> result = new ArrayList<>();
    Interval prev = intervals.get(0);
    for (int i = 1; i < intervals.size(); i++) {
        Interval curr = intervals.get(i);
        if (curr.start <= prev.end) {
            prev.end = Math.max(prev.end, curr.end);
        } else {
            result.add(prev);
            prev = curr;
        }
    }
    result.add(prev);
    return result;
}

6. Duplicate Removal / Grouping

Problem: Group anagrams

List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();
    for (String s : strs) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        String sorted = new String(chars);
        map.computeIfAbsent(sorted, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(map.values());
}

Conclusion

• Basic sorts (Bubble, Selection, Insertion) are excellent for learning but not suitable for large-scale or real-world data.

• Inbuilt sort() (like Java’s Arrays.sort() or Python’s sorted()) is optimized, stable, and adaptive for all real-world use-cases.

• Understanding the right sorting algorithm and combining it with techniques like two pointers, binary search, or greedy strategy is crucial in competitive programming and interviews.