Sorting Algorithms

Koowoy

1. Bubble Sort

In each loop, place the largest number on the top, creating a “bubble”

const bubbleSort = (arr) => {
    for (let i = arr.length - 1; i > 0; i--) {
        let swap = false;
        for (let j = 0; j < i; j++) {
            if(arr[j] > arr[j + 1]) {
                let temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;
                swap = true;
            }
        }
        if(!swap) break; // breaks out of the loop when the array is sorted before the loop as reached the end
    }
    return arr;
}

Bubble sort works fast, when the array is nearly sorted, and the not sorted element is relatively large.

2. Selection Sort

In each loop, place the smallest number at the front of the array.

const selectionSort = (arr) => {
    for (let i = 0; i < arr.length; i++) {
        let min = i;
        for (let j = i + 1; j < arr.length; j++) {
            if(arr[j] < arr[min]) min = j;
        }
        if(i !== min) {
            let temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }
    return arr;
};

Quite similar to bubble sort.

3. Insertion Sort

While looping, create a larger left portion that is sorted.

const insertionSort = (arr) => {
    for (let i = 1; i < arr.length; i++) { // for each element starting from second
        if(arr[i] < arr[i - 1]) { // if element is smaller than previous
            for (let j = i; j > 0; j--) { // go through elements to left until the right place is found
                if(arr[j] > arr[j - 1]) { // if the right place is found, break loop
                    break;
                } else {
                    let temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }
    return arr;
}

4. Merge Sort

Exploit the fact that arrays of 0-1 element are always sorted. Break the array into arrays of single elements, and then merge two of such arrays recursively considering the order.

// array merging helper function
const merge = (arr1, arr2) => {
    let result = []
    let i = 0;
    let j = 0;

    while(i < arr1.length && j < arr2.length) {
        if (arr1[i] > arr2[j]){
            result.push(arr2[j]);
            j++;
        } else if (arr1[i] < arr2[j]) {
            result.push(arr1[i]);
            i++;
        } else {
            result.push(arr1[i]);
            result.push(arr2[j]);
            i++;
            j++;
        }
    }
    // if one array is longer and has finished first, concat rest of the other array
    result = (arr1.length === i) ? result.concat(arr2.slice(j)) : result.concat(arr1.slice(i));
    return result;
}

// split until arrays of 1 element, and come back up merging
const mergeSort = (arr) => {
    if(arr.length === 1) return arr;
    return merge(mergeSort(arr.slice(0, Math.floor(arr.length / 2))), mergeSort(arr.slice(Math.floor(arr.length / 2))));
}

mergeSort([1,8,3,2,9,5,100, 20, 2103, 245, 5,1])

Time Complexity

The amount of time it takes to split arrays = O(log n) The amount of time it takes to merge while comparing each element = O(n) = O(n log n)

5. Quick Sort

Select a random pivot index in the array, fix the position of that pivot. Then recursively do the same procedure with the left and right side of the pivot.

// finding the pivot's correct place to fix
const pivot = (arr, start=0, end=arr.length-1) => {
    let pivotIndex = start;
    const pivot = arr[start]
    for (let i = start + 1; i <= end; i++) {
        if(pivot > arr[i]) {
            pivotIndex++;
            let temp = arr[pivotIndex];
            arr[pivotIndex] = arr[i];
            arr[i] = temp;
        }
    }
    let temp = arr[pivotIndex];
    arr[pivotIndex] = pivot;
    arr[start] = temp;
    return pivotIndex;
}

const quickSort = (arr, left = 0, right = arr.length - 1) => {
    if(left < right){
        let pivotPoint = pivot(arr, left, right);
        quickSort(arr, left, pivotPoint - 1)
        quickSort(arr, pivotPoint + 1, right)
    }
    return arr;
}

Time Complexity

In the worst case for quick sort, which is if the array is already sorted, the time complexity is O(n ^ 2)

Decomposing the array n times X Compare n times

6. Radix Sort

Unlike the other sorting methods, radix sort is not a comparison sort, in that it doesn’t sort the array by comparing the size of each element. Using the characteristics of numbers, sort by placing each element into buckets of 0-9 by the digits starting from the one’s place up.

const getDigit = (num, place) => {
    return Math.floor(Math.abs(num) / (Math.pow(10, place))) % 10;
}

const digitCount = (num) => {
    if(num === 0) return 1;
    return Math.floor(Math.log10(Math.abs(num))) + 1;
}

const mostDigits = (arr) => {
    let max = 0;
    for (let e of arr) {
        let currDigit = digitCount(e)
        max = (max > currDigit) ? max : currDigit;
    }
    return max;
}

const radixSort = (arr) => {
    const loop = mostDigits(arr);
    for(let i = 0; i < loop; i++) {
        let buckets = [[],[],[],[],[],[],[],[],[],[]]
        for(let e of arr) {
            buckets[getDigit(e, i)].push(e);
        }
        arr = buckets.flat();
    }
    return arr;
}