Stanford-Algorithms-Specialization-Coursera

CountingInversions.ts

//
// Divide and Conquer Algorithms, Assignment 2
//

abstract class MergeSort{

    public static inversions: number = 0;

    public static sort(arr: number[]) {
        if (arr.length < 2) return arr;

        let mid_point: number = Math.floor(arr.length / 2);
        let a: number[] = MergeSort.sort(arr.slice(0, mid_point));
        let b: number[] = MergeSort.sort(arr.slice(mid_point));


        // Merge sorted arrays
        let sorted: number[] = [];
        let a_index: number = 0;
        let b_index: number = 0;
        let range: number = a.length + b.length;

        for (let i = 0; i < range; i++){

            if (a_index >= a.length) {
                sorted = sorted.concat(b.slice(b_index));
                break;
            }
            else if (b_index >= b.length) {
                sorted = sorted.concat(a.slice(a_index));
                break;
            }

            if (a[a_index] < b[b_index]) {
                sorted[i] = a[a_index];
                a_index++;
            }
            else {
                sorted[i] = b[b_index];
                b_index++;
                MergeSort.inversions += a.length - a_index;
            }
        }

        return sorted;
    }


}


function solve() {
    let url = 'https://d18ky98rnyall9.cloudfront.net/_bcb5c6658381416d19b01bfc1d3993b5_IntegerArray.txt?Expires=1529625600&Signature=ZyGxKenViVNgt-K51pX1zR213ct1JKuBMLdgS9x7B8icDFFjyCLNBToFwNJVLtZGcF0z3-PQoWFCoU6qGxDC0lCQuND-ViExvsC4A7St9w4UVYSQJUXxeMK6YQrgp28ajOzo8H-TMbo27juqf-q2yk5GpFvJwqbY4lMWSAL4LLA_&Key-Pair-Id=APKAJLTNE6QMUY6HBC5A';
    fetch(url).then(function (data) {
        data.text().then((str) => {
            MergeSort.inversions = 0;
            let arr: number[];
            arr = str.split("\n").map((el) => parseInt(el));
            arr = arr.filter((el)=> !isNaN(el))
            console.log(arr.length);
            MergeSort.sort(arr);
            console.log(MergeSort.inversions);
        }
        ).catch((ex) => console.log(ex));
    });
}

solve();

// console.log(MergeSort.sort([7, 1, 2, 4, 120, 23, 21]))
// console.log(MergeSort.inversions);