Learning Journal

1/25/2024

Relative sort array #2 attempt

Tags: algorithms leetcode selection_sort

function relativeSortArray(arr1: number[], arr2: number[]): number[] {

    let curP = 0;

    for(let i2 = 0; i2 < arr2.length; i2++) {
        const curItem2 = arr2[i2];
        
        for(let i1 = curP; i1 < arr1.length; i1++){
            if(arr1[i1] === curItem2) {
                arr1[i1] = arr1[curP];
                arr1[curP] = curItem2;

                curP++;
            }
        }
    }

    while(curP < arr1.length) {
        for(let i = curP  + 1; i < arr1.length; i++) {
            if(arr1[i] < arr1[curP]) {
                const temp = arr1[i];
                arr1[i] = arr1[curP];
                arr1[curP] = temp;
            }
        }
        curP++ 

    }

    return arr1;
};function relativeSortArray(arr1: number[], arr2: number[]): number[] {

    let curP = 0;

    for(let i2 = 0; i2 < arr2.length; i2++) {
        const curItem2 = arr2[i2];
        
        for(let i1 = curP; i1 < arr1.length; i1++){
            if(arr1[i1] === curItem2) {
                arr1[i1] = arr1[curP];
                arr1[curP] = curItem2;

                curP++;
            }
        }
    }

    while(curP < arr1.length) {
        for(let i = curP  + 1; i < arr1.length; i++) {
            if(arr1[i] < arr1[curP]) {
                const temp = arr1[i];
                arr1[i] = arr1[curP];
                arr1[curP] = temp;
            }
        }
        curP++ 

    }

    return arr1;
};

This is my second attempt for the Relative sort array problem.

Some lessons I learn this time:

Whenever you create a loop, make sure that it stops. At first, I put curP++ in the if block. As a result, curP only move to the next element when there is at least one other element in the rest of the array arr1 that is smaller than the element it points to. If curP points to the smallest element, the if block will never be executed, and thus, curP never reaches the end of the array.

It turns out that in selection sort, we check each element and then move on. We don't need to swap all element, only the elements that are at the wrong place in a sorted array.