Правильны ли мои алгоритмы сортировки?Почему сортировка слиянием занимает меньше итераций, чем быстрая сортировка?

Question

Я экспериментировал с количеством итераций различных алгоритмов сортировки.Я пытался выяснить, какие из них принимают большинство итераций для выполнения.Я определяю итерацию как итерацию в цикле или выполнение функции (чтобы учесть рекурсию).Быстрая сортировка и сортировка слиянием, кажется, намного быстрее, чем Bubble Sort, с точки зрения производительности.Быстрая сортировка кажется более быстрой в тех случаях, когда в массиве меньше элементов.Это может быть потому, что мой алгоритм быстрой сортировки не очень эффективен.

Мой вопрос заключается в том, что быстрая сортировка занимает меньше итераций, чем сортировка слиянием, и если да, то почему.Я также перечислил мой код ниже на случай, если мои алгоритмы неверны.Спасибо.

function quickSort(arr){
        iter++;
        let length = arr.length;
        let pivot_index =  [length-1]; //Math.floor(Math.random() * [length -1]);
    let index = 0;
    while(pivot_index>index){
        iter++;
        if(arr[pivot_index]<arr[index]){
            let temp = arr[index];
            arr[index] = arr[pivot_index-1];
            arr[pivot_index-1] = arr[pivot_index] ;
            arr[pivot_index] = temp;
            --pivot_index
        }
        else
            ++index;
    }

    if(length>3)
        return  quickSort(arr.slice(0, pivot_index)).concat([arr[pivot_index]],quickSort(arr.slice(pivot_index+1)));
    else
        return arr;
}



function selectionSort(arr){
    let numIterations = 0;
    for(let i = 0; i<arr.length-1; i++){
        numIterations+=1;
        for(let j = i +1; j<arr.length; j++){
            if( arr[i] > arr[j]){
                let temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
            numIterations+=1;
        }
    }
    return {"num_iterations": numIterations, "arr":arr}

}


function bubbleSort(arr){

    let numIterations = 0;
    let count = 0;
    do{
        var swapped = false;
        numIterations+=1;
        count+=1;
        for(let i = 0;i<arr.length-count;i++){
            numIterations+=1;
            if(arr[i]>arr[i+1]){
                let temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
                swapped = true;
            }
        }

    } while(swapped == true)
    return {"num_iterations": numIterations, "arr":arr}
}

function mergeSort(arr){
    iter+=1;

    if(arr.length>1){
        let divsor = arr.length + 1;
        let arr_left_half = arr.slice(0,parseInt(divsor / 2));
        let arr_right_half = arr.slice(parseInt( divsor / 2));
        arr = null;
        var tup_arr = [mergeSort(arr_left_half), mergeSort(arr_right_half)];

    }else
        return arr;

    let l = []

    while(tup_arr[0].length > 0 || tup_arr[1].length > 0){
        iter+=1;
        let arr1_length = tup_arr[0].length;
        let arr2_length = tup_arr[1].length;
        if(arr1_length > 0 && arr2_length > 0){
            if(tup_arr[0][0] > tup_arr[1][0])
                l.push(tup_arr[1].shift());
            else
                l.push(tup_arr[0].shift());
        }
        else if( arr1_length > 0)
            l.push(tup_arr[0].shift());
        else if(arr2_length > 0)
            l.push(tup_arr[1].shift())

    }
    tup_arr = null;
    return l;

}

let iter = 0;
let arr = []
for(let i =0;i<10000;i++){
   let num =  Math.floor(Math.random() * 10000);
   arr.push(num);
}

let bubble_sort = bubbleSort(arr.slice());
let selection_sort = selectionSort(arr.slice());
let merge_sort = mergeSort(arr.slice());
console.log("Merge Sort Iterations:"+iter);
iter = 0;
let quick_sort = quickSort(arr.slice());
console.log("Quick Sort Iterations:"+iter);
console.log("Selection Sort Iterations:"+selection_sort.num_iterations);
console.log("Bubble Sort Iterations:"+bubble_sort.num_iterations);

Answer 1

Mergesort всегда возвращается на глубину &lceil;log<sub>2</sub>N&rceil;.На каждом уровне рекурсии каждый элемент сравнивается один раз.

Быстрая сортировка может достичь этого только в том случае, если каждый раз угадывает оптимальное значение разбиения, что маловероятно.Как правило, одна сторона перегородки будет больше, чем другая сторона.Немного уравновешивая увеличенную глубину рекурсии, можно сказать, что после сортировки раздела его элементы больше не сравниваются.Поэтому некоторые элементы сравниваются больше, а другие меньше.Согласно одному правдоподобному определению «среднего случая», быстрая сортировка, как ожидается, будет делать на 40% больше сравнений, чем слияние.

Но быстрая сортировка имеет большое преимущество для больших наборов данных.В сортировке слиянием шаг объединения не может быть выполнен эффективно на месте.Алгоритм зависит от возможности использовать временное хранилище того же размера, что и исходный набор данных.

Так что mergesort, вероятно, лучше, если у вас достаточно свободного места.По крайней мере, так думали авторы glibc, чья реализация qsort выполняет сортировку слиянием, если набор данных не очень большой.