Python 3 Quicksort Implementation Not Working

Question

I Am Running A Test Script to do Quicksort On List Since there are so many ways for partitioning in quicksort and selection of pivot element

i am using here selecting the first index of list as pivot pivot=list[0] and then do sorting pivot_pos=quicksort(list,l,h)

l:Lower Bound & h:Higher/Upper Bound

after returning appropriate index of pivot the list is break into two parts such that:

LEFT PART:quicksort(list,l,pivot_pos-1)&

RIGHT PART:quicksort(list,pivot_pos+1,h)

Since the location of pivot is returned we not include him in next recursion call

The quicksortfunction do partitioning in quick while partition function return index that belong to pivot element.

The Full Code Is Below:

#!/usr/bin/env python3

# quicksort by selecting first element as pivot

def partition(list,l,h):
 pivot=list[l]
 i=l
 j=h

 while(i<=j):
  if list[i]<pivot:
   i+=1
  if list[j]>pivot:
   j-=1
  if (list[i]> pivot and list[j]<pivot):
   list[i],list[j]=list[j],list[i]

 list[j],pivot=pivot,list[j]
 return j

def quicksort(list,l,h):
 if l<h:
  pivot_pos=partition(list,l,h)
  quicksort(list,l,pivot_pos-1)
  quicksort(list,pivot_pos+1,h)



def main():
 list=[] # empty list
 # creating a user defined list
 n=int(input('Define length of array:'))
 for a in range(0,n):
  x=int(input('list{}='.format(a)))
  list.append(x)
 l=0
 h=int(len(list)-1)
 print("l:",l)
 print("h:",h)
 print('Before Sorting:',list)
 quicksort(list,l,h)
 print('After Sorting:',list)

main()

this is good approach of writing quicksort as this not involve too many loop bringing the time complexity to as low as could with this setup

but the code is not working ahead its just stuck you can see o/p hereo/p_of_code

For Those Who Are Unfamiliar With Quicksort Read-It here

The Approach Is Good But The Implemenation Does Not Giving Any O/p Any Suggestionn to Code & improvement is appreciated — CoderWithDIfficulties
– CoderWithDIfficulties, Commented Jul 3, 2021 at 5:15
As an aside, never use list as a variable name in Python, since doing so masks the builtin. This has nothing to do with your problem, but it's something to avoid. — Tom Karzes
– Tom Karzes, Commented Jul 3, 2021 at 5:25
@TomKarzes K I Would Consider this next tym but do you got any solution of this? — CoderWithDIfficulties
– CoderWithDIfficulties, Commented Jul 3, 2021 at 5:27

Tom Karzes · Accepted Answer · 2021-07-03 07:16:19Z

0

Replace your parition with the following:

def partition(lst,l,h):
 pivot=lst[l]
 i=h
 for j in range(h, l, -1):
  if lst[j] > pivot:
   lst[i],lst[j]=lst[j],lst[i]
   i-=1
 lst[i],lst[l]=lst[l],lst[i]
 return i

Note: I completely rewrote this answer. The original answer I posted wasn't right. This is a more standard solution, and I've tested it and it handles all my test cases. This version uses the first element as the pivot.

edited Jul 3, 2021 at 7:16

answered Jul 3, 2021 at 5:43

Tom Karzes

24.3k3 gold badges28 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

CoderWithDIfficulties Over a year ago

@TomKazes Thnx but at the end you are not swaping pivot element to its index i in lst list

CoderWithDIfficulties Over a year ago

@TomKazes i Am not getting it as i and j refrence only swapping values which are lesser and greater than pivot and once the ith index crosses j that index is pivot_postiion now without changing new location of pivot how we are determining the sub array's

CoderWithDIfficulties Over a year ago

@TomKazes It won't once the pivot index is returned the next recurssion followed from (l,pivot_pos-1)&(pivot_pos+1,h)so the next call doesn't contained previous pivot element

CoderWithDIfficulties Over a year ago

@TomKazes I Am agree with You its working great but i am saying from algorithm perspective that we swap pivot only when i crosses j and then swaping pivot element and in the next recursion call we make sure this tym previous pivot not participate although your solution is good and i appreciate it thnx

CoderWithDIfficulties Over a year ago

@TomKazes That's a Very Intiutional Answer Of Solution appreciate it & i see you edit to answer Thnx

|

Collectives™ on Stack Overflow

Python 3 Quicksort Implementation Not Working

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related