Оригинална имплементация на QuickSort
Колеги, здравейте!
Ръчкам въпросния алгоритъм и на страничката в Wikipedia е изписан псевдокод на уж оригиналната имплементация на гн. Hoare (не знам на кирилица как да го изпиша). Това е въпросното нещо:
algorithm quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p)
quicksort(A, p + 1, hi)
algorithm partition(A, lo, hi) is
pivot := A[lo]
i := lo - 1
j := hi + 1
loop forever
do
i := i + 1
while A[i] < pivot
do
j := j - 1
while A[j] > pivot
if i >= j then
return j
swap A[i] with A[j]
За да проверя до колко съм разбрал алгоритъма и къде най-вероятно греша - Защо i започва от lo - 1 ?? още при първия do while нещата умират (поне доколкото аз разбирам). Да вземем например 18, -6, 20, 3, 1, 20, 16 - числата са малко и в реалната имплементация съм сложил да се върти insertionSort-а, но да речем че ще използваме само рекурсиите на quicksort-а за примера.
Така - lo в началото е равно на 0, следователно i == -1. В първия do while, i става i + 1 което е 0, тоест става равно на lo, и при проверката A[ i ] < pivot (където pivot == lo) цикълът спира и левият индекс (въпросното i) остава на 18 и долу swap-а разменя 18 и 16, а не първото 20 и 16 както би трябвало да е. Защо си мисля, че i трябва да започва от lo(pivot), а не от 1 по-надолу. при i == lo, първото сравнение няма да е дали 18 < 18, а -6 <18 и тн и в крайна сметка i ще стигне до 20.
Аз ли бъркам някъде, или това i = lo - 1 е грешно?
Благодаря предварително за търпението и отговорите!
Поздрави!