Learning Journal

1/26/2024

Sort an Array with Shellsort

function sortArray(nums: number[]): number[] {
    let h = 1;

    while(h < nums.length/3) {
        h = 3*h + 1;
    }

    while(h >= 1){
        for(let i = h; i < nums.length;i++) {
            for(let j = i; j >= h && less(nums[j], nums[j-h]); j -= h ) {
                const temp = nums[j];
                nums[j] = nums[j-h];
                nums[j-h] = temp;
            }
        }

        h = Math.floor(h/3);

    }

    return nums;

};

function less(a:number, b:number):boolean {
    return a <= b;
}function sortArray(nums: number[]): number[] {
    let h = 1;

    while(h < nums.length/3) {
        h = 3*h + 1;
    }

    while(h >= 1){
        for(let i = h; i < nums.length;i++) {
            for(let j = i; j >= h && less(nums[j], nums[j-h]); j -= h ) {
                const temp = nums[j];
                nums[j] = nums[j-h];
                nums[j-h] = temp;
            }
        }

        h = Math.floor(h/3);

    }

    return nums;

};

function less(a:number, b:number):boolean {
    return a <= b;
}

This is my attempt to solve the problem Sort an array using shell sort.

Basically, what shellsort does is doing insertion sort but with h interval and then decrease h until h = 1; The idea is that because insertion sort works well in an almost sorted array, we can take advantage of it by giving it an almost sorted array. When we divide the array into some smaller sub-array, it is easy to sort. Thus, we do that by using the h interval. Then, the time h become 1 and thus we do insertion sort, the array is almost sorted.