Pythonでのクイックソートの実装とピボット値の交換

Question

クイックソートを実装する際に、ピボット値を選択することがわかっています。パーティションフェーズでは、ピボット値を右端と交換します。 は、ここに私のコードです：だから問題は、私が代わりにmylistというのピボットを書く場合は、[最初]プログラムは、私はrightmarkをマイリスト[最初]ピボットの代わりに交換しながら値を書き込む場合は、一方に動作していないです

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) 

それただうまく動作します。クイックソート： mylist = [54, 26, 93, 17, 77, 31, 44, 55, 20] sortlist=quicksort(mylist) print(sortlist) その後、出力はいずれも、あなたの最後の質問についてはその

Answer 1

この実装では動作しません：

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

あなたは

pivot = mylist[rightmark] 

を行うときにはmylistを変異されていないのであなたは、単に変数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'] 

同様の理由で3210

、次の操作を実行すると、リストは変更されません：

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

あなたは行う必要があります。

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

それとも、ミューテータメソッドを使用することができます。

最後に、あなたはPythonでスワップを行うためにtemp変数は必要ありません。

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

またはリストと

：

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

Answer 2

が間違っているのか分からない.Don'tです：このまた

が起こっているなぜあなたは私がそのような何かをしようとした場合を教えてもらえます何も返さない。 Thats理由sortlist=quicksort(mylist)は、ソートリストをNoneに設定します。

How do I pass a variable by reference?を読むと、何が起こっているのか理解できます。