Quicksort Implementation In Python

I'm trying to implement quicksort in python. However, my code doesn't properly sort (not quite). For example, on the input array [5,3,4,2,7,6,1], my code outputs [1,2,3,5,4,6,7]. S

Solution 1:

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:

defpartition(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

Solution 2:

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 intailif i < head])
    more = qsort([i for i intailif 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+=1right-=1
        _quicksort(array, start, right)
        _quicksort(array, left, stop)

---

Generating sorted items from an iterable:

defqsort(sequence):
    iterator = iter(sequence)
    try:
        head = next(iterator)
    except StopIteration:
        passelse:
        try:
            tail, more = chain(next(iterator), iterator), []
            yieldfrom qsort(split(head, tail, more))
            yield head
            yieldfrom qsort(more)
        except StopIteration:
            yield head

defchain(head, iterator):
    yield head
    yieldfrom iterator

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

Solution 3:

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.

Solution 4:

Read the Fine Manual :

Quick sort explanation and python implementation :

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

Solution 5:

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.