Cześć! Może mi ktoś powiedzieć, czy dobrze liczę liczbę porównań w procedurze dzielącej Horae na tablicy o takich elementach <14, 13, 12, 11> ?
Algorytm wygląda następująco:
HOARE-PARTITION(A,p,r)
1 x ← A[p]
2 i ← p-1
3 j ← r+1
4 while TRUE do
5 repeat
6 j ← j-1
7 until A[j] ≤ x
8 repeat
9 i ← i+1
10 until A[i] ≥ x
11 if i<j then
12 zamień A[i] ↔ A[j]
13 else
14 zwróć j
Ja to widzę tak:
1 obieg pętli: 6 porównań.
2 obieg pętli: 4 porównania.
3 obieg pętli: 4 porównania.
Co w sumie daje 14 porównań. Czy wszystko jest ok?