Dr._Duck - 1 year ago 67
Python Question

# Implementation of Quick sort in python and exchanging pivot value

We know that while implementing quick sort we select a pivot value.And during the partition phase we exchange pivot value with the rightmark.
Here is my code:

``````def quicksort(mylist):
quicksorthelper(mylist,0,len(mylist)-1)

def quicksorthelper(mylist,first,last):
if first< last:
splitpoint=partition(mylist,first,last)
quicksorthelper(mylist,first,splitpoint-1)
quicksorthelper(mylist,splitpoint+1,last)

def partition(mylist,first,last):
pivot= mylist[first]
leftmark= first +1
rightmark= last
done = False
counter = 0
while not done:
while leftmark <= rightmark and mylist[leftmark]< pivot:
leftmark = leftmark +1
while leftmark <= rightmark and mylist[rightmark]>pivot:
rightmark= rightmark -1

if leftmark>rightmark:
done = True
else:
temp = mylist[leftmark]
mylist[leftmark]=mylist[rightmark]
mylist[rightmark]=temp
counter +=1

temp= pivot                  #pivot = mylist[first]
pivot = mylist[rightmark]
mylist[rightmark]=temp

return rightmark

mylist= [54,26,93,17,77,31,44,55,20]
quicksort(mylist)
print(mylist)
``````

So the problem is if i write pivot instead of mylist[first] the program is not working whereas if i write mylist[first] in place of pivot while exchanging values with rightmark it just works fine. Can you tell me why is this happening

Also if i try to do something like that:
```mylist = [54, 26, 93, 17, 77, 31, 44, 55, 20] sortlist=quicksort(mylist) print(sortlist)```

Then the output is None .Don't know what is wrong with that

This implementation does not work:

``````temp= pivot                  #pivot = mylist[first]
pivot = mylist[rightmark]
mylist[rightmark]=temp
``````

Because you are not mutating `mylist` when you do

``````pivot = mylist[rightmark]
``````

You are simply assigning a new value to the variable `pivot`:

``````>>> i = 2
>>> j = 4
>>> somelist = ['a','b','c','d','e','f','g']
>>> pivot = somelist[i]
>>> pivot
'c'
>>> temp = pivot
>>> pivot = somelist[j]
>>> pivot
'e'
>>> somelist[j] = temp
>>> pivot
'e'
>>> somelist
['a', 'b', 'c', 'd', 'c', 'f', 'g']
``````

For the same reason, doing the following does not change the list:

``````>>> anotherlist = [1, 2, 3]
>>> x = anotherlist[1]
>>> x
2
>>> x = 53
>>> x
53
>>> anotherlist
[1, 2, 3]
``````

You must do:

``````>>> anotherlist[0] = 53
>>> anotherlist
[53, 2, 3]
>>>
``````

Or you could use a mutator method.

Finally, you do not need a `temp` variable to do a swap in Python:

``````>>> a = 42
>>> b = 88
>>> a,b = b,a
>>> a
88
>>> b
42
>>>
``````

Or with a list:

``````>>> somelist = ['a','b','c','d','e','f','g']
>>> i = 2
>>> j = 4
>>> somelist[i], somelist[j] = somelist[j], somelist[i]
>>> somelist
['a', 'b', 'e', 'd', 'c', 'f', 'g']
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download