Как видно из заголовка, у меня возникла ошибка с моим кодом Python Quicksort. Мой код ниже, и это входной файл, который я использую для тестирования.
5
3
8
6
7
4
9
2
1
10
В коде переменная i
является значением границы, а переменная j
является текущейзначение сравнивают с шарниром. Проблема заключается в том, что когда Partition
выполняет свою первую итерацию, значение 3
в массиве не попадает в левую часть значения поворота (в данном случае 5
), как должно. Между прочим, я всегда использую крайний левый индекс.
def Partition(input_array, left_index, right_index):
pivot_value = input_array[left_index]
i = left_index + 1
for j in range(i+1, right_index):
if input_array[j] < pivot_value:
swap(input_array, i, j)
i = i + 1
swap(input_array, left_index, i - 1)
print(input_array)
return i - 1
def swap(input_array, i, j):
input_array[i], input_array[j] = input_array[j], input_array[i]
return input_array
Это массив до первой итерации Partition
:
5, 3, 8, 6, 7, 4, 9, 2, 1, 10
Это массив после первой итерации Partition
:
1, 4, 2, 5, 7, 3, 9, 8 , 6, 10
Как видите, 3
находится в неправильном месте. Любая помощь с этим будет оценена!