quick sort python recursion
21,659
Solution 1
There are numerous problems in your code, here are some fixes just to make it work:
def partition(lst, start, end):
pos = start # condition was obsolete, loop won't
# simply run for empty range
for i in range(start, end): # i must be between start and end-1
if 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 place
return pos
def quick_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):
if len(a) == 0:
return a
p = len(a) // 2
l = [i for i in a if i < a[p]]
m = [i for i in a if i == 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]
def main():
r=len(A)-1
p=0
Result=QuickSort(A,p,r)
print(Result)
def QuickSort(A,p,r):
if p<r:
q=partition(A, p, r)
QuickSort(A, p, q-1)
QuickSort(A, q+1, r)
return A
def partition(A,p,r):
x=A[r]
i=p-1
for j in range(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:
return array
else:
pivot = array[0]
less = quick_sort([i for i in array if i < pivot])
greater = quick_sort([i for i in array if i > pivot])
return less + [pivot] + greater
Author by
user3022418
Updated on July 03, 2021Comments
-
user3022418 almost 3 years
This is my quick sort code, the
partition
function works well, but I got a problem while calling the recursion. Thepos
changes every time it starts the function and then the list limits are change as well. How to fix that?def partition(lst, start, end): pos=0 if len(lst)<2: return for i in range(len(lst[start:end])): if lst[i] < lst[end]: lst[i],lst[pos]=lst[pos],lst[i] pos+=1 elif i==(len(lst[start:end])-1): lst[end],lst[pos]=lst[pos],lst[end] return pos def quick_sort_recursive(lst, start, end): pos=partition(lst, start, end) if start<=pos<=end : quick_sort_recursive(lst, start, pos-1) quick_sort_recursive(lst, pos+1, end) else: return lst
-
shrishinde over 2 yearsfor getting less and greater you are doing list comprehension operation twice on same array. You can improve it to only once. Also if there are duplicate pivot numbers then your code will give wrong answer. e.g. for [6, 6, 5, 8, 2, 1] your code will return only [1, 2, 5, 6, 8]