Learning Journal

1/30/2024

Quick sort

function sortArray(nums: number[]): number[] {
    shuffleArray(nums);
    sort(nums, 0, nums.length - 1);

    return nums;

}

function sort(a:number[], lo:number, hi:number) {
    if(hi <= lo) return;

    let j = partition(a,lo,hi);

    sort(a, lo, j-1);
    sort(a, j + 1, hi);
}

function partition(a:number[], lo:number, hi:number) {
    let i = lo, j = hi + 1;

    while(true) {
        while(a[++i] < a[lo])
            if(i === hi) break;

        while(a[lo] < a[--j])
            if(j === lo) break;

        if(i >= j) break;

        exch(a, i ,j);
    }

    exch(a, lo, j);

    return j;
}

function shuffleArray(a:number[]) {
    for(let i = a.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i +1));
        exch(a, i, j);
    }   
}

function exch(a:number[], i:number, j:number) {
    const temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}
function sortArray(nums: number[]): number[] {
    shuffleArray(nums);
    sort(nums, 0, nums.length - 1);

    return nums;

}

function sort(a:number[], lo:number, hi:number) {
    if(hi <= lo) return;

    let j = partition(a,lo,hi);

    sort(a, lo, j-1);
    sort(a, j + 1, hi);
}

function partition(a:number[], lo:number, hi:number) {
    let i = lo, j = hi + 1;

    while(true) {
        while(a[++i] < a[lo])
            if(i === hi) break;

        while(a[lo] < a[--j])
            if(j === lo) break;

        if(i >= j) break;

        exch(a, i ,j);
    }

    exch(a, lo, j);

    return j;
}

function shuffleArray(a:number[]) {
    for(let i = a.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i +1));
        exch(a, i, j);
    }   
}

function exch(a:number[], i:number, j:number) {
    const temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

This is the solution for the Sort an Array problem using QuickSort.

Basically, what QuickSort does is choose a random element in the array, move all smaller element to the left and all bigger elements to the right, then put that element in the middle. Now, we know that the random element is in its place. Continue to do it for the left and then the right portion of the array util you reach a sub-array of 1.

The job is done in the partition function. We use 2 pointers, one start from the left and the other starts from the right. On the way moving toward each other, when they see some elements that are not in their right sides of the array, swap them.

However, I still don't understand why the pre-decrement and pre-increment play the crucial role in the speed of the algorithm though.