Quicksort implementation in Python

I'm a little confused about what the algorithm's connection to quicksort is. In quicksort, you typically compare all entries against a pivot, so you get a lower and higher group; the quick_sort function clearly expects your partition function to do this.

However, in the partition function, you never compare anything against the value you name pivot. All comparisons are between index i and j, where j is incremented by the for loop and i is incremented if an item was found out of order. Those comparisons include checking an item against itself. That algorithm is more like a selection sort with a complexity slightly worse than a bubble sort. So you get items bubbling left as long as there are enough items to the left of them, with the first item finally dumped after where the last moved item went; since it was never compared against anything, we know this must be out of order if there are items left of it, simply because it replaced an item that was in order.

Thinking a little more about it, the items are only partially ordered, since you do not return to an item once it has been swapped to the left, and it was only checked against the item it replaced (now found to have been out of order). I think it is easier to write the intended function without index wrangling:

def partition(inlist):
    i=iter(inlist)
    pivot=i.next()
    low,high=[],[]
    for item in i:
        if item<pivot:
            low.append(item)
        else:
            high.append(item)
    return low,pivot,high

You might find these reference implementations helpful while trying to understand your own.

Returning a new list:

def qsort(array):
    if len(array) < 2:
        return array
    head, *tail = array
    less = qsort([i for i in tail if i < head])
    more = qsort([i for i in tail if i >= head])
    return less + [head] + more

Sorting a list in place:

def quicksort(array):
    _quicksort(array, 0, len(array) - 1)

def _quicksort(array, start, stop):
    if stop - start > 0:
        pivot, left, right = array[start], start, stop
        while left <= right:
            while array[left] < pivot:
                left += 1
            while array[right] > pivot:
                right -= 1
            if left <= right:
                array[left], array[right] = array[right], array[left]
                left += 1
                right -= 1
        _quicksort(array, start, right)
        _quicksort(array, left, stop)

Generating sorted items from an iterable:

def qsort(sequence):
    iterator = iter(sequence)
    try:
        head = next(iterator)
    except StopIteration:
        pass
    else:
        try:
            tail, more = chain(next(iterator), iterator), []
            yield from qsort(split(head, tail, more))
            yield head
            yield from qsort(more)
        except StopIteration:
            yield head

def chain(head, iterator):
    yield head
    yield from iterator

def split(head, tail, more):
    for item in tail:
        if item < head:
            yield item
        else:
            more.append(item)

If pivot ends up needing to stay in the initial position (b/c it is the lowest value), you swap it with some other element anyway.

Read the Fine Manual :

Quick sort explanation and python implementation :

http://interactivepython.org/courselib/static/pythonds/SortSearch/TheQuickSort.html

Sorry, this should be a comment, but it has too complicated structure for a comment.

See what happens for array being [7, 8]:

• pivot = 7
• i = 1
• for loop does nothing
• array[0] becomes array[i] which is 8
• array[i] becomes pivot which is 7
• you return array[0:1] and pivot, which are [8, 7] and 7 (the third subexpression ignored)...

If you explicitly include the returned pivot in concatenation, you should skip it in the array returned.

okay i "fixed" it, at least on the one input i've tried it on (and idk why... python issues)

def partition(array):   
    pivot = array[0]   
    i = 1   
    for j in range(i, len(array)):   
        if array[j] < pivot:   
            temp = array[i]   
            array[i] = array[j]   
            array[j] = temp   
            i += 1   
    array[0] = array[i-1]  
    array[i-1] = pivot  
    return array[0:i-1], pivot, array[i:(len(array))]  


def quick_sort(array):  
    if len(array) <= 1:  
        return array   

    low, pivot, high = partition(array)  
    #quick_sort (low)  
    #quick_sort (high)  

    return quick_sort (low) + [pivot] + quick_sort (high)  



array = [5,3,4,2,7,6,1]  

print quick_sort(array)  
# prints [1,2,3,4,5,6,7]  

Here it is fixed I added a rev=False flag so you can reverse the sort if you want.:

def partition(array,rev=False):   
    pivot = array[0]   
    i = 1   
    for j in range(i, len(array)):   
        if ((array[j] < pivot) != rev):   
            array[i],array[j] = array[j],array[i]
            i += 1   
    array[0],array[i-1] = array[i-1],pivot
    return array[0:i-1], pivot, array[i:(len(array))]  

def quick_sort(array,rev=False):  
    if len(array) <= 1: return array   
    low, pivot, high = partition(array)  
    if rev: 
       return quick_sort(high,rev) + [pivot] + quick_sort(low,rev)  
    else: 
       return quick_sort(low,rev) + [pivot] + quick_sort(high,rev)

array = [5,3,4,2,7,6,1]  

print (quick_sort(array,rev=False))
# prints [1,2,3,4,5,6,7] 

Here is a tiny, reverse=True quick sort with three part list append. We sort for Less,Equal,Greater than the pivot. I selected a random pivot. You can choose array[0] or array[len(array)//2] as well. Each have their burdens. The ternary selection of which array to append to uses ((x<p) != rev) if rev=False this reads as (x<p) if rev=True this reads as (x>p) so the list is reversed. Also instead of three passes through the list to sort it into buckets:

L = [i for i in arr if ((i<p) != rev)] 
P = [i for i in arr if i==p] 
R = [i for i in arr if ((i>p) != rev)] 

We just have one pass of arr

for x in arr: 
   (L if ((x<p) != rev) else (P if x==p else  R)).append(x)

from secrets import randbelow as rand

def quicksort(arr,rev=False):
   if len(arr) <= 1: return arr # stop recursing
   else:
      L, R, P = [],[],[] # Left, Right and Pivot lists
      p = arr[rand(len(arr))] # or arr[0], arr[-1] 
      for x in arr: 
         (L if ((x<p) != rev) else (P if x==p else R)).append(x)
   return quicksort(L,rev) + P + quicksort(R,rev) 
   
if __name__ == '__main__': 
   R = True
   test_array = [rand(10000 - 1001) + 1000 for i in range(90)]   
   s_array = quicksort(test_array[:],rev=R)
   print(f"Sorted by Quicksort {s_array} ")  

Output looks like:

$ python quicktest.py 
Sorted by Quicksort [9972, 9820, 9817, 9667, 9645, 9582, 9482, 9424, 9420, 9390, 9355, 9333, 9204, 9092, 8844, 8572, 8566, 8456, 8409, 8346, 8337, 8297, 8274, 8191, 8113, 8053, 7875, 7820, 7786, 7785, 7725, 7653, 7301, 7257, 7256, 7247, 6916, 6912, 6844, 6527, 6391, 6373, 6308, 6305, 6295, 6238, 6223, 5951, 5863, 5790, 5707, 5539, 5389, 5383, 5338, 5167, 5101, 4680, 4677, 4589, 4578, 4308, 4240, 4102, 3907, 3892, 3883, 3706, 3609, 3067, 2935, 2934, 2852, 2851, 2589, 2549, 2268, 2245, 2218, 2193, 1876, 1868, 1838, 1837, 1793, 1771, 1610, 1559, 1319, 1300]