Przedstawiony w poprzednim punkcie problem jest szczególnym przypadkiem następującego zadania:

Dany jest ciąg, którego elementy należą do pewnej przestrzeni liniowo uporządkowanej. Niech np. elem będzie typem elementów tego ciągu. Znaleźć k-ty największy element tego ciągu, tzn. element, który ma dokładnie k-1 większych od siebie elementów.

Dla ciągu 3,5,20,7,11,60,32,19,8, drugi największy element to 32, trzeci największy to 20, a czwarty największy element to 19.J

Niech dany ciąg będzie reprezentowany przez tablicę o elementach e[1],...,e[n]. Specyfikacja naszego zadnia może mieć następującą postać:

wk = {istnieje dokładnie k-1 elementów e[j₁],..., e[j_k-1] takich, że result < e[j] dla j= j₁,..., j_k-1.}.

Najprostszy algorytm rozwiązania tego zadania polega na k krotnym wyszukiwaniu maksimum. W przedstawionym tu algorytmie, znalezione kolejno elementy maksymalne są przestawiane na kolejne, początkowe pozycje ciągu. Użyliśmy w tym celu operacji swap(e[i], e[j]), która powoduje zamianę itej i jtej pozycji ciągu. Dokładniej swap(x,y) = {z := x; x := y; y := z}.

K_ty{
	j := 1;
	while (j £ k) do	//e[1]>...>e[j-1], e[j-1]= max{e[j-1],...,e[n]}
	x := j; i := j +1;	//x ma być pozycją elementu największego wśród e[j],...,e[n]
	while (i<n+1) do	// szukamy maksimum wśród elementów na pozycjach >j
	if e[i]> e[x] then x := i fi;
	i := i+1;
	od;	e[x] = max {e[j],...,e[n]}
	swap(e[j],e[x]);	e[1]>...>e[j-1]>e[j], e[j] = max{e[j],...,e[n]}
	j := j + 1;	e[1]>...>e[j-1], e[j-1] = max{e[j-1],...,e[n]}
	od;	// j = k+1
	result := e[k]	//e[1]>...>e[k], e[k] = max{e[k],...,e[n]}
}

Nie będziemy tu dokładniej analizować poprawności tego algorytmu. Komentarze umieszczone obok instrukcji, pozwalają uzasadnić niezmiennik pętli, który mówi, że e[j-1] jest (j-1)szym co do wielkości elementem rozważanego ciągu.

Koszt tego algorytmu, mierzony liczbą wykonanych porównań elementów, to suma kosztów związanych z k krotnym wyszukiwaniem maksimum w coraz krótszych ciągach:

Jeśli k jest małą stałą, to koszt tego algorytmu jest liniowy. Jeśli natomiast k= Q(n), to składnik k*n spowoduje, że funkcja kosztu algorytmu będzie rosła ze wzrostem n, tak jak funkcja kwadratowa.

Czy można rozwiązać problem k-tego co do wielkości elementu taniej, wykonując mniejszą liczbę porównań? C.A.R.Hoare zaproponował algorytm wykorzystujący zasadę "dziel i zwyciężaj".

Niech będzie ciąg e = (6, 4, 1, 8, 7, 3, 2, 5, 9, 0). Przypuśćmy, że szukamy w nim 6 co do wielkości elementu. Niech elementem rozdzielającym będzie pierwszy element ciągu. Tylko 9,7,8 są większe, a elementy 4, 1, 3, 2, 5, 0 są mniejsze od 6.

Wyróżniliśmy pozycję liczby 6, aby zaznaczyć miejsce jakie liczba 6 powinna zająć po uporządkowaniu w porządku rosnącym ciągu e. Zgodnie z punktem 4 algorytmu, szukamy teraz elementu drugiego co do wielkości (6-3-1=2) w ciągu elementów mniejszych, czyli w ciągu 4, 1, 3, 2, 5, 0. Po rozdzieleniu tego ciągu względem 4 otrzymamy 1, 2, 3, 0, 4, 5, bo tylko jeden element jest większy od 4. Na mocy punktu 3 algorytmu Hoare, 4 jest szukanym, szóstym co do wielkości elementem danego ciągu e.

Zupełnie inaczej będzie wyglądał przebieg wyszukiwania, jeżeli jako element rozdzielający weźmiemy ostatni element ciągu, w tym przypadku 0. Wszystkie elementy są większe od 0, zatem po pierwszym rozdzieleniu mamy

Zgodnie z ideą algorytmu Hoare, nadal szukamy elementu szóstego co do wielkości w ciągu elementów większych, tzn. 4, 1, 8, 7, 3, 2, 5, 9, 6. Po ponownym rozdzieleniu względem elementu ostatniego mamy

Ponieważ są trzy elementy większe od 6, zatem należy teraz szukać elementu (6-3-1=2) drugiego co do wielkości wśród elementów mniejszych od 6. Po kolejnym rozdzieleniu ciągu 4, 1, 3, 2, 5,względem ostatniego elementu, otrzymamy 4, 1, 3, 2, 5. Aż cztery elementy są mniejsze od 5, zatem musimy jeszcze raz powtórzyć rozdzielanie. Tym razem rozdzielamy ciąg 4, 1, 3, 2, w poszukiwaniu elementu największego.J

Jedyna trudność w implementacji algorytmu Hoare, to wykonanie punktu 1 z możliwie najmniejszą liczbą porównań i w taki sposób, by zarówno elementy większe jak i mniejsze od elementu rozdzielającego m stanowiły zwarty segment ciągu. Chcemy przecież zastosować do nich ten sam algorytm. Rozdzielanie można zrealizować przepisując wszystkie elementy do tablic pomocniczych, ale nie jest to konieczne. Znane są różne sposoby realizacji zadania rozdzielania. Przykład 6.2 pokazuje jak wiele zależy od wyboru elementu rozdzielającego i sposobu rozdzielania ciągu.

Przedstawimy poniżej algorytm rozdzielania działający w miejscu, tzn. nie wykorzystujący, poza danym ciągiem, żadnej dodatkowej pamięci i używający elementu ostatniego jako elementu rozdzielającego. Algorytm ten zapiszemy w postaci funkcji Partition z dwoma parametrami l, p, wskazującymi lewy i prawy koniec rozważanego fragmentu ciągu, l<p. Wynikiem tej funkcji jest pozycja, którą zajmie w ciągu element rozdzielający, w taki sposób, że na pozycjach starszych znajdują się elementy większe od elementu rozdzielającego, a na pozycjach młodszych, elementy mniejsze lub równe od rozdzielającego. Wynik algorytmu, jak zwykle, zapiszemy na zmiennej result.

wp = {l £ p }, wk = {e[l] £...£e[x-1] £e[x] £ e[x+1] £...£e[p], result = x}.

Warunek początkowy zapewnia tylko, że ciąg ma co najmniej jeden element. Natomiast warunek końcowy ma zapewnić, że dokonaliśmy podziału ciągu w pożądany sposób.

int Partition	(l, p: int){
	x := e[p]; i := l - 1; j := l;	//x jest elementem rozdzielającym
	while (j < p) do	//e[k] £ x dla k=l,... ,i , oraz x £ e[k] dla k=i+1,...,j-1
	if e[j] £ x then
	swap(e[i+1], e[j]);	//e[k] £ x dla k=l,... ,i, i+1 oraz x £ e[k] dla k=i+2,...,j
	i := i+1;	//e[k] £ x dla k=l,... ,i , oraz x £ e[k] dla k=i+1,...,j
	fi;
	j := j+1;	//e[k] £ x dla k=l,... ,i , oraz x £ e[k] dla k=i+1,...,j-1
	od ;	// j=p
	swap(e[i+1],e[p]);	//e[k] £ x dla k=l,... ,i , oraz x £ e[k] dla k=i+1,...,p
	result := i+1; return result
}

Rola wskaźników i, j w algorytmie Partition jest następująca: wszystkie elementy na pozycjach od l do i są mniejsze lub równe x, na pozycjach od i+1 do j-1, są większe od x. Pozostałych miejsc jeszcze nie zbadaliśmy.

Przyjrzyjmy się kolejnym stanom tablicy, do której zastosowano algorytm Partition. Element rozdzielający został zaznaczony kolorem czerwonym. Elementy mniejsze mają kolor żółty, a elementy większe kolor fioletowy. W osobnych kolumnach zapisaliśmy wartości zmiennych i, j.

Każdy wiersz tabeli zawiera stan ciągu po wykonaniu kolejnej iteracji pętli. Gdy j=9 opuszczamy pętlę "while" i wykonujemy zamianę pozycji 4tej i 9tej, umieszczając tym samym element rozdzielający 4 na pozycji czwartej. Na pozycjach mniejszych niż 4 znalazł się elementy mniejsze od rozdzielającego, a na pozycjach większych niż 4 znalazły się elementy większe.J

Poprawność algorytmu Partition: Załóżmy, że po wejściu do pętli "while" (tzn. j<p) spełniony jest warunek g(i,j) postaci:

Jeżeli element na pozycji j-tej (ten o najmniejszym indeksie, którego jeszcze nie zbadaliśmy) jest mniejszy lub równy elementowi rozdzielającemu x, to musimy go umieścić w segmencie elementów £ x. Wykonując operację swap(e[i+1],e[j]), powiększymy segment elementów £ x. Musimy więc uaktualnić wskaźnik i, co robimy wykonując instrukcję i:=i+1. Lista elementów większych kończy się teraz na pozycji jtej. Jednak po wykonaniu instrukcji j:= j+1 nadal spełnione jest g(i,j).

Jeżeli element na pozycji j-tej jest większy od elementu rozdzielającego, to powinien on powiększyć segment elementów > x. Wystarczy więc przesunąć wskaźnik j o jedno miejsce w prawo. Oczywiście, znów spełniona jest formuła g(i,j).

jest niezmiennikiem pętli w algorytmie Partition. Innym niezmiennikiem (uzasadnienie pozostawiamy Czytelnikowi) jest formuła j £ p. Zatem po wykonaniu pętli wartością j jest p oraz spełniony jest warunek końcowy specyfikacji tego algorytmu.

Twierdzenie 6.1 Dla dowolnego niepustego ciągu o elementach z dowolnej struktury danych, która ma określony liniowy porządek, algorytm Partition zatrzymuje się, a otrzymany wynik spełnia warunek końcowy

e[l] £ ... £ e[result-1] £ e[result] £ e[result+1] £ ... £ e[p].

Koszt algorytmu Partition: Liczba porównań wykonanych w procesie rozdzielania zależy od liczby elementów znajdujących się w rozważanej części ciągu. W każdej iteracji pętli "while" wykonujemy tylko jedno porównanie. Pętla "while" jest wykonywana dokładnie p - l razy. Zatem dla ciągu n elementowego koszt algorytmu wynosi: T(Partition,n) = Q(n).

Algorytm Hoare zapiszemy jako algorytm rekurencyjny Hoare(e, l, p,k), którego parametrami są ciąg elementów typu elem, l, p to indeksy lewego i prawego końca fragmentu ciągu, w którym będziemy kontynuować poszukiwania oraz k- numer poszukiwanego elementu. Wynikiem algorytmu jest obiekt typu elem, k-ty największy element ciągu.

elem	Hoare (e: ciąg, l, p, k: int)
{	j := Partition(l,p);	//j jest pozycją elementu rozdzielającego: na prawo elementy niemniejsze, na lewo elementy mniejsze.
	if (p-j = k-1) then result := e[j]	//e[j] jest mniejsze od dokładnie k-1 elementów
	else
	if (p-j>k-1) then	//jest co najmniej k elementów większych od e[j]
	result:=Hoare(e, j+1, p, k);	//e[result] jest k-tym co do wielkości elementem ciągu e[j+1],...,e[p]
	else
	result := Hoare(e, l, j-1, k-(p-j+1);	//e[result] jest k-(p-j+1)-tym co do wielkości elementem ciągu e[l],e[l+1],...e[j-1]
	fi fi
	return e[result]	//e[result] jest k-tym co do wielkości elementem ciągu e
}

Koszt algorytmu Hoare. Algorytm Hoare w najgorszym przypadku może działać tak źle, jak algorytm naiwny. Jeżeli dany ciąg jest uporządkowany rosnąco, to w każdym rekurencyjnym wywołaniu funkcji Partition, liczba elementów mniejszych od rozdzielającego jest zbiorem pustym. Zatem, o ile trzeba kontynuować poszukiwania k-tego co do wielkości elementu, kontynuuje się je w ciągu elementów o jeden krótszym. Biorąc pod uwagę koszt Partition, otrzymujemy (n-1) + (n-2) + ...+(n-k) = kn - k(k+1)/2 porównań w przypadku pesymistycznym. Na szczęście koszt średni algorytmu Hoare jest zdumiewająco dobry. Udowodniono, że średni koszt algorytmu Hoare jest liniowy O(n).

Poprawność: Dokładny dowód poprawności algorytmu Hoare można przeprowadzić przez indukcję ze względu na pewien porządek trójek (l,p,k). My zauważymy tylko, że w wyniku działania Partition spełniony mamy warunek:

Element e[j] jest szukanym k-tym co do wielkości elementem, gdy p- j +1 = k. Rzeczywiście, jedyne większe od e[j] elementy znajdują się na pozycjach j+1,...,p i jest ich wtedy dokładnie k-1. Jeżeli elementów większych od e[j] jest co najmniej k (tzn. p-j>k-1), to szukanie k-tego elementu musimy kontynuować właśnie wśród tych elementów, a elementy mniejsze od e[j] możemy pominąć. Jeżeli elementów większych od e[j] jest niewiele (tzn. p-j <k), to nie ma wśród nich k-tego największego. Co więcej te większe elementy oraz element e[j] możemy pominąć w dalszych rozważaniach i poszukiwać wśród elementów mniejszych od e[j], elementu k-(p-j+1)-tego co do wielkości. Jeżeli wywołania rekurencyjne Hoare(e, j+1, p, k) oraz Hoare(e, l, j-1, k-(p-j+1)) dają poprawne wyniki, to wartość zwracana jako wynik wywołania Hoare(e,l,p,k) jest też ustalona poprawnie.

Pytanie 8: Jaki jest koszt algorytmu Hoare wyszukiwania elementu k-tego co do wielkości w ciągu uporządkowanym rosnąco?

1	2	3	4	5	6	7	8	9	i	j
3	2	6	9	5	1	8	7	4	i = 0	j = 1
3	2	6	9	5	1	8	7	4	i = 1	j = 2
3	2	6	9	5	1	8	7	4	i = 2	j = 3
3	2	6	9	5	1	8	7	4	i = 2	j = 4
3	2	6	9	5	1	8	7	4	i = 2	j = 5
3	2	6	9	5	1	8	7	4	i = 2	j = 6
3	2	1	9	5	6	8	7	4	i = 3	j = 7
3	2	1	9	5	6	8	7	4	i = 3	j = 8
3	2	1	9	5	6	8	7	4	i = 3	j = 9
3	2	1	4	5	6	8	7	9	result = 4
									result = 4