Quick Sort Python Recursion

This is my quick sort code, the partition function works well, but I got a problem while calling the recursion. The pos changes every time it starts the function and then the list

Solution 1:

There are numerous problems in your code, here are some fixes just to make it work:

defpartition(lst, start, end):
    pos = start                           # condition was obsolete, loop won't# simply run for empty rangefor i in range(start, end):           # i must be between start and end-1if lst[i] < lst[end]:             # in your version it always goes from 0
            lst[i],lst[pos] = lst[pos],lst[i]
            pos += 1

    lst[pos],lst[end] = lst[end],lst[pos] # you forgot to put the pivot# back in its placereturn pos

defquick_sort_recursive(lst, start, end):
    if start < end:# this is enough to end recursion
        pos = partition(lst, start, end)
        quick_sort_recursive(lst, start, pos - 1)
        quick_sort_recursive(lst, pos + 1, end)
                                          # you don't need to return the list# it's modified in place

Example:

example = [3,45,1,2,34]
quick_sort_recursive(example, 0, len(example) - 1)
print example

Gives:

python test.py

[1, 2, 3, 34, 45]

Solution 2:

I think in a pure recursive implementation the partition aux function is not needed:

def quicksort_recursive(a):
    iflen(a) == 0:
        returnap= len(a) // 2
    l = [i for i in a if i < a[p]]
    m = [i for i in a ifi== a[p]]
    r = [i for i in a if i > a[p]]
    return quicksort_recursive(l) + m + quicksort_recursive(r)

Solution 3:

Trivial example of Quick Sort algorithm:

*

###  QUICKSORT
A=[44,5,22,0,323,995,94,4,7,15]
defmain():
    r=len(A)-1
    p=0
    Result=QuickSort(A,p,r)
    print(Result)
defQuickSort(A,p,r):

    if p<r:
        q=partition(A, p, r)
        QuickSort(A, p, q-1)
        QuickSort(A, q+1, r)
    return A
defpartition(A,p,r):
    x=A[r]
    i=p-1for j inrange(p,r):
        if A[j]<=x:
            i=i+1
            a,b=A.index(A[i]), A.index(A[j])
            A[a],A[b]=A[b],A[a]
    d,c=A.index(A[i+1]),A.index(A[r])
    A[c],A[d]=A[d],A[c]
    return i+1
main()

*

Solution 4:

recursive Quicksort algorithm

def quick_sort(array):
    if len(array) < 2:
        returnarrayelse:
        pivot = array[0]
        less = quick_sort([i for i in arrayif i < pivot])
        greater = quick_sort([i for i in arrayif i > pivot])
        return less + [pivot] + greater

Solution 5:

def qsort(array):
    if not array:
        return []

    p, *xs = array
    lesser = [x for x in xs if p<x]
    greater = [x for x in xs if p>=x]

    return qsort(lesser) + [p] + qsort(greater)

qsort([3, -5, 3, 5, 1, 7, 8, 2, -2])

The approach is not very different from Luis Sobrecueva. I would argue its slightly more pythonic.