Is this a legit Quicksort implementation, and what is its complexity?

Question

I was trying to program a quicksort, and here's my result. It's in Javascript, and it definetely sorts the lists. However, I realized that most Quicksort algorithms I've seen online are very different from this, it feels like my algorithm came too easy to program compared to what I've seen online, therefore I got doubtful.

I'm fully aware that this algorithm is very inefficient in terms of memory, because it creates new lists (new memory allocation) instead of doing in-place sorting. But I'm more interested in teaching this algorithm to a friend, that's why I'm trying to program the simplest version possible. So my question is, is this a legit (right implementation) of the Quicksort algorithm? or does it do something else? (Remember: I'm not asking if this is efficient because I know it isn't!)

Also, what is the complexity of this algorithm? I tried to calculate it, and my analysis was: In every iteration, assuming that both lists (left and right) have an equal number of elements, this generates a recursive tree with depth logN and because in every level of the tree, if we sum up all the array traversal, we end up with N iterations, then, that means that for every level, we have N iterations, and therefore a complexity of O(N Log N). That's the best case, and the worst case is when the tree gets all unbalanced due to bad partitioning, ending up in O(N^2) complexity. Is this analysis right?

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));

}

This seems correct but a very simple (probably the most simple) implementation of quicksort. It seems you are aware of the large space complexity so I won't go there. Your Big-O seems correct as well. Btw, that `middle` pivot can be replaced with the first or last element of array for simplicity if that's what you are looking for. — Amin J, Sep 27 '16 at 00:34

score 0 · Answer 1 · edited May 23 '17 at 12:09

Yes, this is a very widely accepted functional version of Quicksort.

Consider a version of quicksort written in Haskell (taken from 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

First the elements are partitioned into two groups: smallerSorted and biggerSorted, and then each partition is sorted recursively, and then concatentated. Average case is O(nlogn) and worst case is O(n²).

Related question: Why is the minimalist, example Haskell quicksort not a “true” quicksort?

score 0 · Answer 2 · answered Sep 27 '16 at 00:35

0

Average case performance O(n log n) Worst case space complexity O(n) auxiliary (naive) O(log n) auxiliary (Sedgewick 1978)

answered Sep 27 '16 at 00:35

peterbest69

49
10

score 0 · Answer 3 · answered Sep 27 '16 at 00:42

I think your implementation is neat and easy to understand. It's fine, enough to teach your friend! The average performance is O(NlogN) and the worst case is O(N^2)

There are many different versions choosing "pivot" or improved ones as you've mentioned.

Below is another "in-place" version for quicksort.

 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)

Is this a legit Quicksort implementation, and what is its complexity?

3 Answers3