Python 3-way partitioning (Quicksort)

Question

Я пытаюсь написать код на Python для 3-way-раздела, однако я получаю ошибку индексации. Я попытался это исправить, но, похоже, не преуспел. В моем коде я выбираю первую запись, которая является точкой опоры, а затем сканирую ее слева и справа, при необходимости меняя значения. Если какая-либо запись равна оси, я либо перемещаю ее в начало, либо в конец (где я получаю сообщение об ошибке).

Это мой код

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 

и определяет своп как:

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

, когда я пытаюсь запустить эту функцию, я получаю ошибку в строке 21, что индекс вне диапазона. Какие-либо предложения о том, что здесь не так?

Answer 1

Как указано в комментариях к вопросу, функция swap() в вашем коде ничего не делает. В Python имена - это просто метки, прикрепленные к объектам. Если вы назначаете имя, вы просто прикрепляете ярлык к объекту. Когда вы передаете объект функции, объект передается, а не имена, назначенные ему. Задания внутри функции создают только локальные имена для объекта, но не имеют видимого эффекта вне функции.

Вы можете изменить объекты, переданные в функцию. Следующее осуществление swap() будет работать:

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

Он изменяет список, переданный в качестве a.