Learning Journal

1/31/2024

QuickSort :: 2nd attempt

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

    return nums;
}


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

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

    const pivotI = partition(nums, lo, hi);

    sort(nums, lo, pivotI - 1);
    sort(nums, pivotI + 1, hi);

}


function partition(a:number[], lo:number, hi:number) {
    let leftP = lo, rightP = hi + 1;
    const pivotP = lo;
    
    while(true) {
        while(a[++leftP] < a[pivotP]) 
            if(leftP === hi) break;

        while(a[--rightP] > a[pivotP])
            if(rightP === lo) break;

        if(leftP >= rightP) break;

        swap(a, leftP, rightP);
    }

    swap(a, pivotP, rightP);

    return rightP;
}

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

    return nums;
}


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

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

    const pivotI = partition(nums, lo, hi);

    sort(nums, lo, pivotI - 1);
    sort(nums, pivotI + 1, hi);

}


function partition(a:number[], lo:number, hi:number) {
    let leftP = lo, rightP = hi + 1;
    const pivotP = lo;
    
    while(true) {
        while(a[++leftP] < a[pivotP]) 
            if(leftP === hi) break;

        while(a[--rightP] > a[pivotP])
            if(rightP === lo) break;

        if(leftP >= rightP) break;

        swap(a, leftP, rightP);
    }

    swap(a, pivotP, rightP);

    return rightP;
}

function swap(nums:number[], i:number,j:number):void {
    const temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

This is my second attempt at using QuickSort to solve the Sort an Array problem Here is what I learned.

What happens right before `hi` crosses `lo`?

On the iteration right before hi crosses lo, they are next to each other. In other words, we have hi === lo + 1. Then, in the partition function, leftP is assigned to lo then increases by one and reaches hi, thus a[leftP] > a[pivotP], the loop stops. Also, in the partition function, rightP is assigned to hi +1, then decreases by one, still greater than pivot, decreases by one again, now it equals to lo, less than pivot and stops. The if statement right after that escapes the while(true) loop,then the pivot is swap with lo. Now, we have pivot === lo, thus, the first sort returns because hi < lo and the second sort returns because hi === lo.

Why the statement `if(leftP >= rightP) break;` is put inside the while loop?

Because two while loops right before it can make the two pointers cross each other. If there is not the if statement right there to stop, the swap statement right after that can mess thing up.

QuickSort :: 2nd attempt

What happens right before hi crosses lo?

Why the statement if(leftP >= rightP) break; is put inside the while loop?

What happens right before `hi` crosses `lo`?

Why the statement `if(leftP >= rightP) break;` is put inside the while loop?