8. Sort Array nlogn

8. Sort an Array

Sort an Array - LeetCode

Quick Sort with 1 pivot: failed → worst O(n^2)

Time: Time over

Space:

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
    quickSort(nums, 0, nums.length - 1);
    return nums;
};

function quickSort(arr, left, right) {
    if (left >= right) {
        return arr;
    }

    const pivotIndex = partition(arr, left, right);
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
    return arr;
}

function partition(arr, left, right) {
    let pivot = right;
    let pointer = left;
    while (left < pivot) {
        if (arr[left] < arr[pivot]) {
            swap(arr, pointer, left);
            pointer++;
            console.log(pointer)
        }
        left++;
    }
    swap(arr, pointer, pivot);

    return pointer;
}

function swap(arr, a, b) {
    const temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
    return arr;
}

Quick Sort with 2 pivots ⇒ good when duplicates

One-Pivot Quick Sort and Three-Way Partition Quick Sort for Duplicates, w. Explanation | 36 ms, Java - Sort an Array - LeetCode

import java.util.Random;

class Solution {
    private static Random random;

    private static class Partition {
        int left;
        int right;
        Partition() {}
        Partition(int left, int right) {
            this.left = left; 
            this.right = right;
        }
    }
    
    public int[] sortArray(int[] nums) {
        random = new Random(1);
        Solution.quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    private static void quickSort(int[] nums, int start, int end) {
        if (start < end) {
            Partition partition = threeWayPartition(nums, start, end);
            quickSort(nums, start, partition.left - 1);
            quickSort(nums, partition.right + 1, end);
        }
    }

    private static Partition threeWayPartition(int[] nums, int start, int end) {
        int pivotIndex = start + random.nextInt(end - start + 1);
        int pivotValue = nums[pivotIndex];
        swap(nums, start, pivotIndex);

        // Loop invariant:
        // 1. [start, lt): strictly less than pivotValue
        // 2. [lt, cur) : equal to pivotValue
        // 3. [cur, gt] : unexplored
        // 4. (gt, end] : strictly larger than pivotValue
        int lt = start + 1;
        int cur = start + 1;
        int gt = end;
        while(cur <= gt) {
            if (nums[cur] < pivotValue) {
                swap(nums, lt, cur);
                lt++;
                cur++;
            } else if (nums[cur] == pivotValue) {
                cur++;
            } else if (nums[cur] > pivotValue) {
                swap(nums, cur, gt);
                gt--;
            }
        }
        // At exit, the partition is [start, lt), [lt, gt], (gt, end].
        return new Partition(lt, gt);
    }

    private static void swap(int[] nums, int i , int j) {
        if (i == j)
            return;
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}

Merge Sort

Time: O(nlogn)

Space: O(N^2)

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    const arr = mergeSort(nums, 0, nums.length - 1);
    return arr;
};

function mergeSort(arr, s, e) {
    if ( s === e) 
        return [arr[s]];
    
    const m = s + Math.floor((e - s) / 2);
    const left = mergeSort(arr, s, m);
    const right = mergeSort(arr, m + 1, e);

    const merged = merge(left, right);
    return merged;
}

function merge(arr1, arr2) {
    let idx1 = 0;
    let idx2 = 0;

    const merged = [];
    while (idx1 < arr1.length && idx2 < arr2.length) {
        if (arr1[idx1] < arr2[idx2]) {
            merged.push(arr1[idx1]);
            idx1++;
        } else {
            merged.push(arr2[idx2]);
            idx2++;
        }
    }

    while (idx1 < arr1.length) {
        merged.push(arr1[idx1]);
        idx1++;
    }

    while (idx2 < arr2.length) {
        merged.push(arr2[idx2]);
        idx2++;
    }

    return merged;
}

function swap(arr, a, b) {
    [arr[b], arr[a]] = [arr[a], arr[b]];
}

using temp array

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    const arr = mergeSort(nums, 0, nums.length - 1);
    return arr;
};

function mergeSort(arr, s, e) {
    if (s >= e) {
        return arr;
    }
    const m = s + Math.floor((e - s) / 2);
    mergeSort(arr, s, m);
    mergeSort(arr, m + 1, e);
    merge(arr, s, m, e);

    return arr;
}

function merge(arr, left, mid, right) {
    if (left >= right) {
        return arr;
    }

    const len = right - left + 1;
    const temp = new Array(len).fill(0);
    
    let i = left;
    let j = mid + 1;

    let pointer = 0;
    while (i <= mid && j <= right) {
        if (arr[i] < arr[j]) {
            temp[pointer] = arr[i];
            i++;
        } else {
            temp[pointer] = arr[j];
            j++;
        }
        pointer++;
    }

    while (i <= mid) {
        temp[pointer] = arr[i];
        i++;
        pointer++;
    }

    while (j <= right) {
        temp[pointer] = arr[j];
        j++;
        pointer++;
    }

    // replace
    for (let i = 0; i < len; i++) {
        arr[i + left] = temp[i];
    }

    // console.log(temp)

    return arr;
}

function mergeSort1(arr, s, e) {
    if ( s === e) 
        return [arr[s]];
    
    const m = s + Math.floor((e - s) / 2);
    const left = mergeSort(arr, s, m);
    const right = mergeSort(arr, m + 1, e);

    const merged = merge(left, right);
    return merged;
}

function merge1(arr1, arr2) {
    let idx1 = 0;
    let idx2 = 0;

    const merged = [];
    while (idx1 < arr1.length && idx2 < arr2.length) {
        if (arr1[idx1] < arr2[idx2]) {
            merged.push(arr1[idx1]);
            idx1++;
        } else {
            merged.push(arr2[idx2]);
            idx2++;
        }
    }

    while (idx1 < arr1.length) {
        merged.push(arr1[idx1]);
        idx1++;
    }

    while (idx2 < arr2.length) {
        merged.push(arr2[idx2]);
        idx2++;
    }

    return merged;
}

function swap(arr, a, b) {
    [arr[b], arr[a]] = [arr[a], arr[b]];
}

Heap Sort

Time: buildHeap: O(nlogn) remove: O(logn)

Space: O(n)

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    const minHeap = new Heap(nums);
    const arr = [];
    while (minHeap.heap.length !== 0) {
        arr.push(minHeap.remove());
    }

    return arr;
};

class Heap {
    constructor(arr, predicate = (a, b) => a <= b ? true : false) {
        this.predicate = predicate;
        this.heap = this.buildHeap(arr);
    }

    buildHeap(arr) {
        let currentIndex = Math.floor((arr.length - 1 - 1) / 2);
        while (currentIndex >= 0) {
            this.siftDown(arr, currentIndex, arr.length - 1);
            currentIndex--;
        }

        return arr;
    }

    insert(v) {
        this.heap.push(v);
        this.siftUp(this.heap, this.heap.length - 1);
    }

    remove(v) {
        this.swap(this.heap, 0, this.heap.length - 1);
        const elementToRemove = this.heap.pop();
        this.siftDown(this.heap, 0, this.heap.length - 1);
        return elementToRemove;
    }

    siftUp(heap, currentIndex) {
        let parentIndex = Math.floor(( currentIndex - 1) / 2 );
        while (parentIndex >= 0) {
            if (this.predicate(heap[parentIndex], heap[currentIndex])) {
                break;
            }
            this.swap(heap, parentIndex, currentIndex);
            currentIndex = parentIndex;
            parentIndex = Math.floor(( currentIndex - 1) / 2 );
        }
    }

    siftDown(heap, currentIndex, endIndex) {
        let left = currentIndex * 2 + 1;
        while (left <= endIndex) {
            let min = left;
            const right = currentIndex * 2 + 2;
            if (heap[right] !== undefined && this.predicate(heap[right], heap[min])) {
                min = right;
            }

            const flag = this.predicate(heap[currentIndex], heap[min]);
            if  (flag) break;

            this.swap(heap, currentIndex, min);
            currentIndex = min;
            left = currentIndex * 2 + 1;
        }
    }

    swap(arr, a, b) {
        [arr[b], arr[a]] = [arr[a], arr[b]];
    }
}