quick sort python recursion

Question

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

Community · Accepted Answer · 2020-06-20 09:12:55Z

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]

Luis Sobrecueva · Accepted Answer · 2019-03-04 16:36:19Z

4

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)

answered Mar 4, 2019 at 16:36

Luis Sobrecueva

6901 gold badge6 silver badges13 bronze badges

Comments

Nafisa Israil · Accepted Answer · 2021-07-02 11:42:26Z

2

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

edited Jul 2, 2021 at 11:42

answered Oct 9, 2019 at 6:30

Nafisa Israil

1492 silver badges4 bronze badges

1 Comment

shrishinde Over a year ago

for 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]

Prox · Accepted Answer · 2015-01-16 22:51:57Z

1

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

*

answered Jan 16, 2015 at 22:51

Prox

111 bronze badge

Comments

muhsin mohammed · Accepted Answer · 2019-12-02 05:10:06Z

1

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.

edited Dec 2, 2019 at 5:10

answered Dec 2, 2019 at 5:04

muhsin mohammed

3212 silver badges3 bronze badges

Comments

Israel Manzo · Accepted Answer · 2020-10-08 00:04:40Z

1

~Returning recursively the partitions~

def quick_sort(nums):
  less = []
  equal = []
  greater = []
  
  if len(nums) > 1: # array len greater than 1 the exe
    pivot = nums[len(nums) // 2] #pivot at mid point
    for i in nums:
      if i < pivot: less.append(i)
      elif i == pivot: equal.append(i)
      elif i > pivot: greater.append(i)
    return quick_sort(less) + equal + quick_sort(greater)
  else:
    return nums # else return array

answered Oct 8, 2020 at 0:04

Israel Manzo

3433 silver badges8 bronze badges

Comments

Andy Richter · Accepted Answer · 2025-02-22 20:23:28Z

This will also reverse sort. It uses one pass through the partial array to set left[], pivot[] and right[]. It does use arr[0] as a pivot. Many like mid or random pivots. Change it if you want. I used a single ternary operation to append to the correct list. On my machine it sorts 250,000 element list in about 2 seconds.

Call it like:

new = quicksort(test_array,False) # or True to reverse sort

Here is the code:

def quicksort(arr,rev=False):
   r = -1 if rev else 1
   if len(arr) <= 1: return arr # stop recursing
   else:
      L, P, R = [],[],[] # Left,Pivot and Right
      p = arr[0] # or arr[len(arr)//2] or arr[-1] 
      for x in arr: 
         (L if x*r<p*r else (P if x==p else R)).append(x)
      return quicksort(L,rev) + P + quicksort(R,rev)

Here it is with pivot in the middle. Notice the big change ;-)

def quicksort(arr,rev=False):
   r = -1 if rev else 1
   if len(arr) <= 1: return arr # stop recursing
   else:
      L, P, R = [],[],[] # Left,Pivot and Right
      p = arr[len(arr)//2] # or arr[0] or arr[-1] 
      for x in arr: 
         (L if x*r<p*r else (P if x==p else R)).append(x)
      return quicksort(L,rev) + P + quicksort(R,rev)

Collectives™ on Stack Overflow

quick sort python recursion

7 Answers 7

Comments

Comments

1 Comment

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

7 Answers 7

Comments

Comments

1 Comment

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related