Learning Journal

2/6/2024

QuickSort - 3rd attempt

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

    return nums;
}


function quicksort(nums:number[], lo:number, hi:number) {
    if(lo >= hi) return;
    
    const pivotI = partition(nums, lo, hi);

    quicksort(nums, lo, pivotI - 1);
    quicksort(nums, pivotI + 1, hi);
}



function partition(nums:number[], lo:number, hi:number):number {
    const pivotI = lo;
    let pL = pivotI, pR = hi + 1;
    
    while(true) {
        while(nums[++pL] < nums[pivotI]) if(pL === hi) break;
        while(nums[--pR] > nums[pivotI]) if(pR === lo) break;

        if(pR <= pL) break;
        swap(nums, pL, pR);
    }

    swap(nums, pR, pivotI);

    return pR;    
}



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

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

    return nums;
}


function quicksort(nums:number[], lo:number, hi:number) {
    if(lo >= hi) return;
    
    const pivotI = partition(nums, lo, hi);

    quicksort(nums, lo, pivotI - 1);
    quicksort(nums, pivotI + 1, hi);
}



function partition(nums:number[], lo:number, hi:number):number {
    const pivotI = lo;
    let pL = pivotI, pR = hi + 1;
    
    while(true) {
        while(nums[++pL] < nums[pivotI]) if(pL === hi) break;
        while(nums[--pR] > nums[pivotI]) if(pR === lo) break;

        if(pR <= pL) break;
        swap(nums, pL, pR);
    }

    swap(nums, pR, pivotI);

    return pR;    
}



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

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

Finally, I understand why we must move the left and right pointers first and then compare. If we do it in the reverse order, we won't know anything about the element that the pointers are currently pointing to when we do the swap, which might cause problems.

Always remember to set the base case in a recursive function. The base case in quick sort is when lo crosses hi (lo >= hi).

Revised by chatGPT

Understanding Quicksort Partitioning: In the quicksort algorithm, the partition function is integral. It works by selecting a pivot element and ensuring all elements less than the pivot are on its left, and all greater are on its right. The process involves moving the left (pL) and right (pR) pointers inward and swapping elements to maintain this order.

It's essential to increment (or decrement) pL (or pR) before comparing the values with the pivot. This way, we ensure we're examining a fresh element in each iteration and avoiding potential issues that could arise if we swapped elements without properly assessing them. Not adhering to this sequence could disrupt the algorithm's logic, leading to incorrect positioning of elements relative to the pivot.

Base Case in Recursion: In recursive functions, establishing a base case is vital to prevent infinite recursion. In quicksort, the base case occurs when the sub-array has zero or one element, which we check by ensuring lo does not surpass hi (lo >= hi). When this condition is met, the function returns without making further recursive calls, ensuring the algorithm eventually terminates after sorting the array segment within the given bounds.

Remembering these core principles helps maintain the efficiency and correctness of the quicksort algorithm.