0

Even though I am getting correct partition but the output is not correct.It seems that it's not able to recollect its recursive output.

def Quick_Sort(alist):
  if len(alist)>0:
    print(alist)  
    pivot=alist[-1]
    pivotindex=0
    for i in range(len(alist)-1):
        if alist[i]<pivot:

            alist[i],alist[pivotindex]=alist[pivotindex], alist[i]
            pivotindex +=1
    alist[pivotindex],alist[-1] = alist[-1], alist[pivotindex]
    print(alist) 
    Quick_Sort(alist[:pivotindex])
    Quick_Sort(alist[pivotindex+1:])

alist =input('enter list:')
alist=list(map(int,alist.split()))

Quick_Sort(alist)
print(alist)

output.............................................................

enter list:4 2 5 3 6 9 1
[4, 2, 5, 3, 6, 9, 1]
[1, 2, 5, 3, 6, 9, 4]
[2, 5, 3, 6, 9, 4]
[2, 3, 4, 6, 9, 5]
[2, 3]
[2, 3]
[2]
[2]
[6, 9, 5]
[5, 9, 6]
[9, 6]
[6, 9]
[9]
[9]
[1, 2, 5, 3, 6, 9, 4]
Willem Van Onsem
  • 443,496
  • 30
  • 428
  • 555
Karan Purohit
  • 459
  • 3
  • 8
  • 16
  • 1
    `alist[:pivotindex]` does *not* construct a view, but a copy. So changes to the copy are not reflected to the real list, so the recursive calls, have no effect. – Willem Van Onsem Dec 25 '17 at 17:27
  • If you'll notice, the result you see is basically the output of the first partition operation, and nothing more. What you need to pass to the recursive calls are indices to operate on, `l` and `r`. Passing copies will not affect the original in any way. – cs95 Dec 25 '17 at 17:30
  • Here's my favourite QS implementation with python: https://stackoverflow.com/questions/18262306/quicksort-with-python – cs95 Dec 25 '17 at 17:31

1 Answers1

0

Try this code:

def Quick_Sort(alist):
  if len(alist)>0:
    print(alist)  
    pivot=alist[-1]
    pivotindex=0
    for i in range(len(alist)-1):
        if alist[i]<pivot:

            alist[i],alist[pivotindex]=alist[pivotindex], alist[i]
            pivotindex +=1
    alist[pivotindex],alist[-1] = alist[-1], alist[pivotindex]
    print(alist) 
    alist = Quick_Sort(alist[:pivotindex])
    alist = Quick_Sort(alist[pivotindex+1:])
  return alist

alist =input('enter list:')
alist=list(map(int,alist.split()))

Quick_Sort(alist)
print(alist)
Arvindsinc2
  • 716
  • 7
  • 18