Witam, chcę zliczyć liczbę kopiowań i porównań dla tablicy A = {11,12,13,14} algorytmu szybkiego sortowania z procedurą dzielącą w wersji Lomuto.
Mam pseudokod tego
Lomuto-Partition(A, p, r)
x = A[r]
i = p - 1
for j = p to r - 1
if A[j] <= x
i = i + 1
swap( A[i], A[j] )
swap( A[i +1], A[r] )
return i + 1
No i z tego co tutaj widzę to wszystkie pozostałe elementy są porównywane z ostatnim (x) więc wychodziłoby na to, że będą 3 porównania. Zgadza się?
3 porównania to będą dla pierwszego wywołania Lomuto-Partition. Pamiętaj że QuickSort jest algorytmem rekurencyjnym, więc musisz sprawdzić i wywołania rekurencyjne.
@Wibowit, mógłbyś to rozpisać ? Jako porównanie traktuję tylko pętle "if" czy może sprawdzenie warunku "p < r-1" również ?
Pozdrawiam.
ps. Nie chciałem zakładać nowego tematu skoro już taki istnieje.
Generalnie liczy się tylko porównania elementów, nie indeksów. Mając 4 elementy wybierasz element dzielący i porównujesz go z pozostałymi trzema. Następnie ewentualnie wywołujesz dalsze operacje rekurencyjnie.
Wychodzą mi 3 porównania. Algorytm zwraca 4 jako i+1, żadne wartości nie są zmienione, zamieniam ze sobą te same elementy czyli nic się nie zmienia. Jak mam teraz wejść w tą rekurencję ?
W sortowaniu szybkim jest rekurencja. W podanym algorytmie podziału nie ma rekurencji.
Wyszło mi 6 porównań zarówno dla 1234 jak i 4321.. Czy do chociaz jednego jest to poprawny wynik ?
Chyba tak. Najlepiej zaimplementować algorytm, a potem zliczać porównania za pomocą opakowania ich w wywołanie następującej funkcji:
bool zliczPorównanie(bool wynik) = {
globalnyLicznikPorównań++;
return wynik;
}
Wtedy masz natychmiastowe potwierdzenie obliczeń.