Guided Project: Sorting I

Bubble Sort

Example Implementation

                        public static int[] bubbleSort(int[] arr) {
    int len = arr.length;
    boolean swapped;
    do {
        swapped = false;
        for (int i = 0; i < len - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                swapped = true;
            }
        }
    } while (swapped);
    return arr;
}
                    

Time & Space Complexity:

Time Complexity: O(n²) - Nested loops result in quadratic time complexity
Space Complexity: O(1) - Only uses a constant amount of extra space

Example Usage:

int[] numbers = {64, 34, 25, 12, 22, 11, 90};
System.out.println(Arrays.toString(bubbleSort(numbers))); // [11, 12, 22, 25, 34, 64, 90]

Insertion Sort

Example Implementation

                        public static int[] insertionSort(int[] arr) {
    int len = arr.length;
    for (int i = 1; i < len; 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;
    }
    return arr;
}
                    

Time & Space Complexity:

Time Complexity: O(n²) in worst case, but can be O(n) if array is nearly sorted
Space Complexity: O(1) - In-place sorting algorithm

Example Usage:

int[] numbers = {12, 11, 13, 5, 6};
System.out.println(Arrays.toString(insertionSort(numbers))); // [5, 6, 11, 12, 13]

Algorithm Comparison

Algorithm	Best Case	Average Case	Worst Case	Space	Stable
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Yes

When to Use:

Bubble Sort: Simple implementation and good for educational purposes, but rarely used in practice due to inefficiency with large datasets.
Insertion Sort: Efficient for small datasets or nearly sorted arrays. Often used as part of more complex algorithms.

Practice Challenges

Challenge 1: Optimize Bubble Sort

Modify the bubble sort algorithm to skip comparisons for already sorted elements at the end of the array.

                        public static int[] optimizedBubbleSort(int[] arr) {
    // Your code here
    return arr;
}
                    

Challenge 2: Sort Objects by Property

Extend insertion sort to work with an array of objects, sorting by a specified property.

                        public static void insertionSortByProperty(Object[] array, String propertyName) {
    // Your code here
}
                    

Example:

class Person {
    String name;
    int age;
    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
}
Person[] people = {
    new Person("John", 30),
    new Person("Alice", 25),
    new Person("Bob", 35)
};
// Example: sort by age (implement logic in insertionSortByProperty)
insertionSortByProperty(people, "age");
// Output: [{ name: 'Alice', age: 25 }, { name: 'John', age: 30 }, { name: 'Bob', age: 35 }]

Additional Resources:

If you want more practice with sorting algorithms, check out these resources: