5 Sorting Algorithms for Coding Interviews

function partition(arr, start = 0, end = arr.length - 1) {
    // Let's choose the pivot to be the arr[start] element
    let pivot = arr[start];
    let swapIdx = start;

    for (let i = start + 1; i <= end; i++) {
        if (arr[i] < pivot) {
            swapIdx++;
            // Swap current element with the element at the new
            // pivot index
            [arr[i], arr[swapIdx]] = [arr[swapIdx], arr[i]];
        }
    }
  
    // Swap the pivot element with the element at the pivot index
    [arr[swapIdx], arr[start]] = [arr[start], arr[swapIdx]];
  
    // Return the index of the pivot element after swapping
    return swapIdx;
}

// Recursive
function quickSort(arr, left = 0, right = arr.length - 1) {
    // Base case is that the left and right pointers don't overlap,
    // after which we'll be left with an array of 1 item
    if (left < right) {
        let pivotIndex = partition(arr, left, right);
      
        // For left subarray, which is everything to the left
        // of the pivot element
        quickSort(arr, left, pivotIndex - 1);
      
        // For the right sub array, which is everything to the
        // right of the pivot element
        quickSort(arr, pivotIndex + 1, right);
    }
    // Return the array, when it's of length 1 i.e, left === right
    return arr;
}

function merge(arr1, arr2) {
    // Make a new array, and 2 pointers to keep track of elements of
    // arr1 and arr2     
    let res = [],
        i = 0,
        j = 0;
    
    // Loop until either arr1 or arr2 becomes empty
    while (i < arr1.length && j < arr2.length) {
        // If the current element of arr1 is lesser than that of
        // arr2, push arr1[i] and increment i         
        if (arr1[i] < arr2[j]) {
            res.push(arr1[i]);
            i++;
        } else {
            res.push(arr2[j]);
            j++;
        }
    }

    // Add the rest of the remining subarray, to our new array
    while (i < arr1.length) {
        res.push(arr1[i]);
        i++;
    }
    while (j < arr2.length) {
        res.push(arr2[j]);
        j++;
    }
    return res;
}

// Recursive merge sort
function mergeSort(arr) {
    // Base case
    if (arr.length <= 1) return arr;
  
    // Splitting into two halves
    let mid = Math.floor(arr.length / 2);
    let left = mergeSort(arr.slice(0, mid));
    let right = mergeSort(arr.slice(mid));
  
    // merging the two sorted halves
    return merge(left, right);
}

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
      
        // Start comparing current element with every element before it
        for (let j = i - 1; j > -1; j--) {
          
            // Swap elements as required
            if (arr[j + 1] < arr[j]) {
                [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]];
            }
        }
    }
    return arr;
}

// Create Max Heap
function maxHeap(arr, i) {
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    let max = i;

    if (left < arrLength && arr[left] > arr[max]) {
        max = left;
    }

    if (right < arrLength && arr[right] > arr[max]) {
        max = right;
    }

    if (max != i) {
        swap(arr, i, max);
        maxHeap(arr, max);
    }
}

function swap(arr, i, j) {
    const temp = arr[i];

    arr[i] = arr[j];
    arr[j] = temp;
}

function heapSort(arr) {
    arrLength = arr.length;

    for (let i = Math.floor(arrLength / 2); i >= 0; i -= 1) {
        maxHeap(arr, i);
    }

    for (i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i);
        arrLength--;

        maxHeap(arr, 0);
    }
    return arr;
}

function bubbleSort(arr) {
    let noSwaps;
    for (let i = arr.length; i > 0; i--) {
        noSwaps = true;
        for (let j = 0; j < i - 1; j++) {
            if (arr[j + 1] < arr[j]) {
                // Swap
                [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]];
                // Make 'noSwaps' false
                noSwaps = false;
            }
        }
        // End the iterations if there were no swaps made in one full pass
        if (noSwaps) {
            break;
        }
    }
    return arr;
}