✅ Day 4: Sorting Algorithms (Basic to Intermediate)

🎯 Goals for Today

• Understand how sorting works and why it’s needed

• Learn and implement:

  • Bubble Sort

  • Selection Sort

  • Insertion Sort

• Analyze time & space complexities

• Practice beginner sorting problems

---

📘 1. Why Sorting Matters

Sorting helps:

• Optimize searching (e.g., binary search)

• Solve problems like duplicates, frequency, etc.

• Prepare data for algorithms like two pointers, greedy, divide & conquer, etc.

---

🔁 2. Sorting Algorithms

🔹 Bubble Sort

Repeatedly swap adjacent elements if they are in the wrong order.

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

• Time Complexity: Worst → O(n²), Best → O(n) (already sorted)

• Space: O(1)

---

🔹 Selection Sort

Find the minimum element and put it at the beginning.

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // swap
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

• Time Complexity: Always O(n²)

• Space: O(1)

---

🔹 Insertion Sort

Build the sorted array one element at a time by inserting elements at the correct position.

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int current = arr[i];
            int j = i - 1;

            while (j >= 0 && arr[j] > current) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = current;
        }
    }
}

• Time Complexity: Best → O(n), Worst → O(n²)

• Space: O(1)

---

🧠 3. Sorting Algorithm Comparison Table

Algorithm	Time Complexity (Best / Avg / Worst)	Space	Stable?
Bubble Sort	O(n) / O(n²) / O(n²)	O(1)	✅
Selection Sort	O(n²) / O(n²) / O(n²)	O(1)	❌
Insertion Sort	O(n) / O(n²) / O(n²)	O(1)	✅

🔍 4. Practice Problems

Try these:

• Sort an array of 0s, 1s, and 2s (Dutch National Flag)

• Check if an array is sorted and rotated

• Count the number of swaps required to sort the array

• Sort a nearly sorted (k-sorted) array

You can also implement a custom comparator or reverse order sort (forward-thinking Java practice).

---

📚 Homework for Day 4

✅ Implement all three sorting algorithms
✅ Solve 2 sorting-based problems from LeetCode:

• Sort Colors

• Check if Array Is Sorted and Rotated

Would you like solutions for these 2 LeetCode problems?

---

⏭️ What’s Coming on Day 5:

• Advanced Sorting: Merge Sort, Quick Sort

• Time Complexity Analysis

• Recursion involved in sorting