0

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

Dr._Duck
  • 125
  • 1
  • 12

2 Answers2

2

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']
juanpa.arrivillaga
  • 88,713
  • 10
  • 131
  • 172
0

Regarding your last question: quicksort does not return anything. Thats why sortlist=quicksort(mylist) sets sortlist to None.

Read How do I pass a variable by reference? to understand whats going on.

Community
  • 1
  • 1
dahrens
  • 3,879
  • 1
  • 20
  • 38
  • Yeah i have figured that out. Also their is on more issue. the pivot value exchange. Do you know whats the problem here – Dr._Duck Oct 29 '16 at 10:24
  • the SO question and answer I've posted are related to the value exchange. Can you add the changed part which is not working additionally to your question? i do not really get the point :) – dahrens Oct 29 '16 at 10:31
  • Just see the comment in my code # pivot = mylist[first] so in those particular three lines if i write pivot instead of mylist[first] the program is not working . Although i have already assigned pivot = mylist[first] in the start of the partition function – Dr._Duck Oct 29 '16 at 10:36
  • but you do not use `mylist[first]` at all in those three lines - what do I miss? – dahrens Oct 29 '16 at 10:48
  • Yes i have not and that is the reason the program is not working. If i replace pivot with mylist[first] the program will work. The thing is i know the solution to my problem that only thing i don't know is why is this happening – Dr._Duck Oct 29 '16 at 11:10