品一品プログラミング---5

1261 ワード

問題の説明:
配列ベースsortソート関数の実装
var sort = function(arr) {
    // your code
}

sort([5, 100, 6, 3, -12]) //[-12, 3, 5, 6, 100]

手順は次のとおりです.
//泡立ちソートO(n^2)
var sort = function(arr) {
    var len = arr.length
    for(var i = 0; i < len-1; i++) {
        for(var j = i+1; j < len; j++) {
            if(arr[i] > arr[j]) {
                var tmp = arr[i]
                arr[i] = arr[j]
                arr[j] = tmp
            }
        }
    }
    return arr
}

//クイックソート---メリット:その場でソートO(n*log 2 n)
var quickSort = function(arr) {
    function sort(left,right) {
        var high = right;
        var pivot = arr[left];
        if(right > left){
            while(left < right) {
                while(left < right && arr[right] > pivot) {
                    right--;
                };
                arr[left] = arr[right];
                while(left < right && arr[left] < pivot) {
                    left++;
                }
                arr[right] = arr[left];
            }
            arr[left] = pivot;
            sort(0, left);
            sort(left+1, high);
        }
    }
    sort(0,arr.length-1);
    return arr;
}