Implement Quicksort in Python

Question

I am trying to implement quicksort in python. However, my code is not sorting correctly (not really). For example, on the input array [5,3,4,2,7,6,1] my code outputs [1,2,3,5,4,6,7]. So, the end result fits 4 and 5. I admit I'm a bit rusty in python since I was learning ML (and before that was pretty new to python). I know other python quicksort implementations and other similar questions about the stack overflow about python and quicksort, but I'm trying to figure out what's wrong with this piece of code that I wrote myself:

#still broken 'quicksort'

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

def quick_sort(array):
    if len(array) <= 1: #if i change this to if len(array) == 1 i get an index out of bound error
        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,5,4,6,7]

Answer 1

, quicksort. quicksort , ; quick_sort , .

, . j, j for, , . . , , . , , , , , , , ; , , , , , , , .

, , , , , (, , ). , :

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

Answer 2

, .

---

:

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

---

:

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)

---

:

def qsort(sequence):
    iterator = iter(sequence)
    head = next(iterator)
    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)

Answer 3

pivot (b/c ), - .

Answer 4

:

python:

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

Answer 5

, , .

, [7, 8]:

• pivot = 7
• = 1
• for
• array[0] array[i], 8
• array[i] pivot, 7
• array[0:1] pivot, [8, 7] 7 ( )...

pivot , .

Answer 6

okay "" , , , ( idk, ... python)

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]