IndexError при реализации quicksort CS50 style

Question

Как кто-то, довольно новый для программирования, я пытаюсь реализовать quicksort в Python. Тем не менее, я пытаюсь реализовать его таким образом, который не кажется наиболее распространенным. Я использую технику, описанную в этом видео, CS50: https://www.youtube.com/watch?v=aQiWF4E8flQ

Эта версия алгоритма выбирает стержень в конце массива, размещает «стену» в начале и начинает итерирование списка. Когда он находит элемент, который меньше, чем ось, он меняет этот предмет на предмет с правой стороны стены и перемещает стену на одну позицию вправо. Когда все предметы сравниваются с осью опоры, он устанавливает шарнир на стене, а стена перемещается на одну позицию вправо. Это продолжается до тех пор, пока стена не окажется в конце массива.

До сих пор, я пришел с этим:

def quicksort(alist): 
    quicksort_helper(alist) 
    print alist 

def quicksort_helper(alist): 
    wall = 0 
    while wall < (len(alist) - 1): 
     pivot = len(alist) - 1   
     for current in range(wall, pivot): 
      if alist[current] < alist[pivot]: 
       alist[current], alist[wall] = alist[wall], alist[current] 
       wall = wall + 1 
      alist[wall], alist[pivot] = alist[pivot], alist[wall] 
      wall = wall + 1 

Когда я пытаюсь запустить программу, которую я держать возникают проблемы с массивом указателей стены и опоры, так как это сообщение об ошибке I я получаю:

IndexError: list index out of range 

Я пробовал много с индексами, но я не могу понять это.

Answer 1

Quicksort работает следующим образом: вы сначала разбиваете свой массив так, что есть три подмассива: левый массив содержит все элементы, которые меньше, чем pivod, ни в каком порядке. Средний «массив» - это всего лишь один элемент, свод *. Правильный массив содержит все элементы, которые больше или равны оси.

Теперь известно, что стержень находится в правильном положении. Затем вам нужно отсортировать левый и правый подмассивы.

Разделение осуществляется с помощью стены. Положение стержня фиксировано; это всегда самый правый элемент. Затем вы объединяете каждый элемент со стержнем и перемещаете его слева от стены, если он меньше. Вы должны переместить стену прямо в другой, чтобы освободить место для элемента.

После того, как вы просмотрели все элементы, у вас есть три подмассива, но в неправильном порядке: влево, вправо, вправо. (Стена - это барьер между левым и правым подмассивами.) Чтобы привести его в правильном порядке, поменяйте элемент справа от стены с помощью шарнира, но не перемещайте стену. Это нужно сделать только один раз, после цикла секционирования. (Обратите внимание, что если опорный элемент является самым большим элементом, вы меняете своп с собой, что вполне нормально, если расточительно.)

Ваш алгоритм использует 0 и гравитацию массива как привязанную. Это работает для всего массива. Когда вы хотите сортировать подмассивы, вам нужно настроить эти границы. Поэтому неплохо передать границы помощнику быстрой сортировки, чтобы вы могли вернуться. (Это sutomary, чтобы включить нижнюю границу включительно, а верхнюю границу исключить, так же как индекс len(a) является за пределами допустимого диапазона индексов для a, когда индексирование начинается с нуля.)

Вот рабочий раствор:

def quicksort(alist): 
    quicksort_helper(alist, 0, len(alist)) 

def quicksort_helper(alist, l, r): 
    if l < r: 
     wall = l 

     pivot = r - 1 

     for current in range(wall, pivot): 
      if alist[current] < alist[pivot]: 
       alist[current], alist[wall] = alist[wall], alist[current] 
       wall = wall + 1 

     alist[wall], alist[pivot] = alist[pivot], alist[wall] 

     quicksort_helper(alist, l, wall) 
     quicksort_helper(alist, wall + 1, r) 

*) Существует три способа Quicksort, что группы все цапф одного и того же значения вместе с тем, чтобы улучшить плохую работу QuickSort с массивами, которые имеют лишь несколько уникальных элементы.

Answer 2

Линия alist[wall], alist[pivot] = alist[pivot], alist[wall] выполняется, в некоторых случаях, после того, как wall значение было увеличено, и в результате len(alist), который вызывает IndexError.

Вы можете использовать pdb для отладки кода, добавить строку import pdb;pdb.set_trace() в свою функцию для отслеживания значений переменных.