Guided Project: Sorting I

Bubble Sort

Example Implementation

                        function bubbleSort(arr) {
    const len = arr.length;
    let swapped;
    
    do {
        swapped = false;
        
        for (let i = 0; i < len - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                // Swap elements
                [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
                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:

const numbers = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(numbers)); // [11, 12, 22, 25, 34, 64, 90]

Insertion Sort

Example Implementation

                        function insertionSort(arr) {
    const len = arr.length;
    
    for (let i = 1; i < len; i++) {
        // Store the current element to be compared
        let current = arr[i];
        let j = i - 1;
        
        // Compare current with sorted elements and shift them to make space
        while (j >= 0 && arr[j] > current) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        // Place current in the correct position
        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:

const numbers = [12, 11, 13, 5, 6];
console.log(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.

                        function optimizedBubbleSort(arr) {
    // Your code here
}
                    

Challenge 2: Sort Objects by Property

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

                        function insertionSortByProperty(array, propertyName) {
    // Your code here
}
                    

Example:

const people = [
    { name: 'John', age: 30 },
    { name: 'Alice', age: 25 },
    { name: 'Bob', age: 35 }
];

console.log(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: