Python 3ウェイ・パーティショニング（Quicksort）

Question

3ウェイ・パーティション用のPythonコードを作成しようとしていますが、索引付けエラーが発生します。私はそれを修正しようとしましたが、成功しないようです。私のコードでは、最初の項目をピボットにしてから、必要に応じて値を入れ替えて左から右へスキャンします。いずれかの項目がピボットと等しい場合は、最初に移動するか、最後に移動します（ここではエラーが発生します）。

これは私のコード

def partition(a, start, end): 
    left=start+1 
    right=end 
    p=start+1 
    q=end 
    pivot=a[start] 
    while True: 
     while a[left]<pivot: 
      left+=1 
     while a[right]>pivot: 
      right-=1 
      if right==start+1: 
       break 
     if left>=right: 
      break 
     swap(a[left], a[right]) 
     if a[left]==pivot: 
      swap(a[p],a[left]) 
      p+=1 
     if a[right]==pivot: 
      swap(a[right], a[q]) 
      q-=1 
    swap(a[right], a[start]) 
    k=end 
    while k>=q+1: 
     swap(a[left+1], a[k]) 
     k-=1 
     left+=1 
    k=1 
    while k<p: 
     swap(a[k], a[right+1]) 
     k+=1 
     right-=1 

と私は思いとしてスワップを定義する：範囲外のそのインデックス、私はこの機能を実行しようとすると、私は21行でエラーが出ます

def swap(a, b): 
    temp=a 
    a=b 
    b=temp 

。ここに何が間違っているかに関する提案はありますか？

Answer 1

質問のコメントに記載されているように、コード内のswap()関数は何も行いません。 Pythonでは、名前は単にオブジェクトに付けられたラベルです。名前に割り当てる場合は、オブジェクトにラベルを付けるだけです。オブジェクトを関数に渡すと、そのオブジェクトには割り当てられた名前ではなく、そのオブジェクトが渡されます。関数内の代入は、オブジェクトのローカル名のみを作成しますが、関数の外には目に見える効果はありません。

オブジェクトに変更されたオブジェクトは変更できます。 swap()の次の実装では動作します：

def swap(a, i, j): 
    a[i], a[j] = a[j], a[i] 

それはaとして渡されたリストを変更します。