Является ли это законной реализацией Quicksort и какова его сложность?

Question

Я пытался запрограммировать quicksort, и вот мой результат. Это в Javascript, и он определенно сортирует списки. Тем не менее, я понял, что большинство алгоритмов Quicksort, которые я видел в Интернете, сильно отличаются от этого, похоже, что мой алгоритм слишком прост в программировании по сравнению с тем, что я видел в Интернете, поэтому я сомневаюсь.

Я полностью осознаю, что этот алгоритм очень неэффективен с точки зрения памяти, поскольку он создает новые списки (новое распределение памяти) вместо того, чтобы выполнять сортировку на месте. Но меня больше интересует преподавание этого алгоритма другу, поэтому я пытаюсь запрограммировать простейшую версию. Поэтому мой вопрос заключается в том, что это законная (правильная реализация) алгоритма Quicksort? или он делает что-то еще? (Помните: я не спрашиваю, эффективен ли это, потому что я знаю, что это не так!)

Кроме того, какова сложность этого алгоритма? Я попытался вычислить его, и мой анализ был: на каждой итерации, предполагая, что оба списка (слева и справа) имеют равное количество элементов, это генерирует рекурсивное дерево с глубиной logN и потому, что на каждом уровне дерева, если мы суммируем весь обход массива, мы заканчиваем N итерациями, то это означает, что для каждого уровня мы имеем N итераций и, следовательно, сложность O (N Log N). Это лучший случай, и худший случай - когда дерево получает все несбалансированное из-за плохого разбиения, заканчивая сложностью O(N^2). Правильно ли этот анализ?

function quicksort(list){ 


    var size = list.length; 


    // Base cases 
    if(size == 0) return [];  
    if(size == 1) return [list[0]]; 


    // Get the pivot as the middle element 
    var middle = Math.floor(size/2);  
    var pivot = list[middle]; 

    // Init two lists. Left = less than pivot. Right = greater than pivot. 
    var list_left = []; 
    var list_right = []; 


    // Push every element of the list into either the left or right list 
    for(i=0; i<size; i++){  

     if(i == middle) continue; // Skip the pivot 


     if(list[i] <= pivot) 
      list_left.push(list[i]); 
     else   
      list_right.push(list[i]); 
    } 

    // Return the concatenation of the quicksorted left list 
    // pivot, and quicksorted right list (here's the recursion) 

    return quicksort(list_left).concat(pivot).concat(quicksort(list_right)); 

} 

Answer 1

Да, это очень широко распространенная функциональная версия Quicksort.

Рассмотрим вариант сортировки, написанный на Haskell (взятый из Learn You A Haskell):

quicksort :: (Ord a) => [a] -> [a] 
quicksort [] = [] 
quicksort (x:xs) = 
    let smallerSorted = quicksort [a | a <- xs, a <= x] 
     biggerSorted = quicksort [a | a <- xs, a > x] 
    in smallerSorted ++ [x] ++ biggerSorted 

Сначала элементы разбиты на две группы: smallerSorted и biggerSorted, а затем каждый раздел отсортированный рекурсивно, и затем объединяется. Средний случай - O (nlogn), а наихудший - O (n).

Связанные вопрос: Why is the minimalist, example Haskell quicksort not a “true” quicksort?

Answer 2

Средняя производительность случае O (п журнал п) худшем случае пространства сложность O (N) вспомогательное (наивный) O (журнал N) вспомогательное (Седжвик 1978)

Answer 3

Я думаю, ваша реализация аккуратна и понятна. Это нормально, достаточно, чтобы научить вашего друга! Средняя производительность - O (NlogN), а наихудший вариант - O (N^2)

Существует много разных вариантов, которые выбирают «поворот» или улучшенные, как вы уже упоминали.

Ниже приведена другая версия «на месте» для быстрой сортировки.

function partition(a, left, right, pivotIndex) 
pivotValue := a[pivotIndex] 
swap(a[pivotIndex], a[right]) 
storeIndex := left 
for i from left to right-1 
    if a[i] <＝ pivotValue 
     swap(a[storeIndex], a[i]) 
     storeIndex := storeIndex + 1 
swap(a[right], a[storeIndex]) 
return storeIndex 

procedure quicksort(a, left, right) 
if right > left 
    select a pivot value a[pivotIndex] 
    pivotNewIndex := partition(a, left, right, pivotIndex) 
    quicksort(a, left, pivotNewIndex-1) 
    quicksort(a, pivotNewIndex+1, right)