<|start_filename|>sort/mergeSort.js<|end_filename|>
function merge(a, p, q, r) {
    //console.log("p=%s; q=%s; r=%s", p, q, r);

    let n1 = q - p + 1;
    let n2 = r - q;
    let left = [];
    let right = [];

    for (let i = 0; i < n1; i++) {
        left[i] = a[p + i];
    }

    for (let j = 0; j < n2; j++) {
        right[j] = a[q + j + 1];
    }

    left.push(Number.MAX_VALUE);
    right.push(Number.MAX_VALUE);

    let i = 0;
    let j = 0;

    for (let k = p; k <= r; k++) {
        if (left[i] <= right[j]) {
            a[k] = left[i];
            i++;
        } else if (right[j]) {
            a[k] = right[j];
            j++;
        }
    }
}

function mergeSort(a, p, r) {
    if (p < r) {
        let q = Math.floor((p + r) / 2);
        mergeSort(a, p, q);
        mergeSort(a, q + 1, r);
        merge(a, p, q, r);
    }
}

module.exports = function (a) {
    mergeSort(a, 0, a.length - 1);
};


<|start_filename|>sort/bubbleSort.js<|end_filename|>
module.exports = function (a) {
    for (let i = 0; i < a.length; i++)
        for (let j = a.length; j > i; j--)
            if (a[j] < a[j-1])
                [a[j], a[j-1]] = [a[j-1], a[j]];
};


<|start_filename|>exercises/exercise237.js<|end_filename|>
// Exercise 2.3-7
// s is a set of positive integers (excluding zero).
// check if two numbers exist in s which sum is equal to x
function check(s, x) {
    let a = [];
    for (let i = 0; i < s.length; i++) {
        let v = s[i];
        if (v < x) {
            a[v] = 1;
        }
    }

    let q = Math.floor(x / 2) - 1;
    for (let i = x-1; i >= q; i--) {
        let j = x - i;
        //console.log("i=%s; j=%s; x=%s", i, j, x);
        if (i !== j && a[i] === 1 && a[j] === 1) {
            return true;
        }
    }
    return false;
}



let s = [1, 3, 4, 5];

let test = (x) => console.log(`${x}: ${check(s, x)}`);

for (let i = 1; i < 11; i++) {
    test(i);
}


<|start_filename|>search/binarySearch.js<|end_filename|>
module.exports = function (v, a) {
    // assume a is sorted

    function binarySearch(v, a, i, j) {
        if (i === j) {
            return a[i] === v ? i : -1;
        }

        let k = Math.floor((j - i) / 2) + i;

        //console.log("binarySearch: i=%s; j=%s; k=%s; v=%s", i, j, k, v);

        if (a[k] === v) {
            return k;
        }

        if (a[k] < v) {
            return binarySearch(v, a, k + 1, j);
        }

        return binarySearch(v, a, i, k - 1);
    }

    return binarySearch(v, a, 0, a.length);
};


<|start_filename|>sort/selectionSort.js<|end_filename|>
module.exports = function selectionSort(a) {
    for (var j = 0; j < a.length - 1; j++) {
        let k = j;
        for (var i = j + 1; i < a.length; i++) {
            if (a[i] < a[k]) {
                k = i;
            }
        }
        let tmp = a[j];
        a[j] = a[k];
        a[k] = tmp;
    }
};


<|start_filename|>sort/insertionSort.js<|end_filename|>
module.exports = function insertionSort(a) {
    for (var j = 1; j < a.length; j++) {
        let val = a[j];
        let i = j - 1;
        while (i >= 0 && a[i] > val) {
            a[i + 1] = a[i];
            i -= 1;
        }
        a[i + 1] = val;
    }
};


<|start_filename|>search/run.js<|end_filename|>
let binarySearch = require("./binarySearch.js");

let numbers = [0, 1, 2, 3, 4, 5, 6, 7];

let index = binarySearch(3, numbers);

console.log("Index found:", index);


<|start_filename|>sort/run.js<|end_filename|>
let insertionSort = require("./insertionSort.js");
let selectionSort = require("./selectionSort.js");
let mergeSort = require("./mergeSort.js");
let bubbleSort = require("./bubbleSort.js");


let numbers = [8, 4, 2, 3, 1, 7, 3];

//insertionSort(numbers);
//selectionSort(numbers);
//mergeSort(numbers);
bubbleSort(numbers);

console.log("Result: ", numbers);
