/*
 *  The some classical sorting algorithms, implement with JavaScript
 *  Author: mengshi
 *  Date: 2018.05.12
 */

/*
 * Name: bubble sort
 * Time: O(n^2), best ~ O(n), worst ~ O(n^2)
 * Space: O(1)
 * Stability: yes
 * Feature: exchange algorithms
 */
function bubble(arr) {
    for (var i=0; i < arr.length; i++) {
        for (var j=arr.length; j >= i j--) {
            if (arr[j] > arr[j+1]) {
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
            }
        }
    }

    return arr;
}

/*
 * Name: select sort
 * Time: O(n^2), best ~ O(n^2), worst ~ O(n^2)
 * Space: O(1)
 * Stability: yes
 * Feature: select algorithms
 */
function select(arr) {
    for (var i=0; i < arr.length; i++) {
        var min = i;
        for (var j=arr.length; j > i; j--) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }

        if (i != min) {
            [arr[i], arr[min]] = [arr[min], arr[i]]
        }
    }

    return arr;
}

/*
 * Name: insert sort
 * Time: O(n^2), best ~ O(n), worst ~ O(n^2)
 * Space: O(1)
 * Stability: yes
 * Feature: insert algorithms
 */
function insert_sort(arr, step) {
    for (var i = step; i < arr.length; i+=step) {
        var mi = i;

        while (mi-step >= 0 && arr[mi-step] > arr[mi]) {
            [arr[mi], arr[mi-step]] = [arr[mi-step], arr[mi]];
            mi-=step;
        }
    }
}

function insert(arr) {
    insert_sort(arr, 1);
}

/*
 * Name: shell sort
 * Time: O(nlogn) ~ O(n^2), best ~ O(nlogn), worst ~ O(n^2)
 * Space: O(1)
 * Stability: no
 * Feature: insert algorithms
 */
function shell(arr) {
    var l = arr.length;

    while ((l = parseInt(l/2)) >= 1) {
        insert_sort(arr, l);
    }
}

/*
 * Name: merge sort
 * Time: O(nlogn), best ~ O(nlogn), worst ~ O(nlogn)
 * Space: O(n)
 * Stability: yes
 * Feature: merge algorithms
 */
function merge_sort(left, right) {
    var temp = []

    while (left.length > 0 && right.length > 0) {
        var x = left.shift(), y = right.shift()
        if (x <= y) {
            temp.push(x);
            right.unshift(y);
        } else {
            temp.push(y);
            left.unshift(x);
        }
    }

    if (left.length == 0) {
        return temp.concat(right);
    } else {
        return temp.concat(left);
    }
}

function merge(arr) {
    if (arr.length <= 1) {
        return arr;
    }

    var left  = arr.slice(0, arr.length/2);
    var right = arr.slice(arr.length/2);

    return merge_sort(merge(left), merge(right));
}

/*
 * Name: heap sort
 * Time: O(nlogn), best ~ O(nlogn), worst ~ O(nlogn)
 * Space: O(1)
 * Stability: no
 * Feature: select algorithms
 */
function heap_adjust(arr, l, n) {
    var temp = arr[l];

    for(var j = l*2; j <= n; j*=2) {
        if (j < n && arr[j] < arr[j+1]) {
            j++;
        }

        if (temp >= arr[j]) {
            break;
        }

        arr[l] = arr[j];
        l = j;
    }

    arr[l] = temp;
}

function heap(arr) {
    var n = arr.length - 1
    for (var l = parseInt(n/2); l >= 0; l--) {
        heap_adjust(arr, l, n);
    }

    for (; n >= 0; n--) {
        [arr[0], arr[n]] = [arr[n], arr[0]]
        heap_adjust(arr, 0, n-1);
    }
}

/*
 * Name: quick sort
 * Time: O(nlogn), best ~ O(nlogn), worst ~ O(n^2)
 * Space: O(logn) - O(n)
 * Stability: no
 * Feature: exchange algorithms
 */
function partition(arr, low, high) {
    var key = arr[low];

    while (low < high) {
        while (low < high && arr[high] >= key) {
            high--;
        }
        [arr[low], arr[high]] = [arr[high], arr[low]];

        while (low < high && arr[low] <= key) {
            low++;
        }
        [arr[low], arr[high]] = [arr[high], arr[low]];
    }

    return low;
}

function quick_sort(arr, low, high) {
    if (low < high) {
        pivot = partition(arr, low, high);

        quick_sort(arr, low, pivot-1);
        quick_sort(arr, pivot+1, high);
    }
}

function quick(arr) {
    quick_sort(arr, 0, arr.length-1);
}

/*
 * program main function
 */
function main() {
    var arr = new Array(50, 10, 90, 30, 70, 40, 80, 60, 20);

    shell(arr);
    console.info(arr);
}

main();