Dany jest n elementowy podzbiór X pewnego liniowo porządkowanego zbioru E. Przyjmijmy, że elementy zbioru X znajdują się w tablicy TAB o elementach TAB[1],...,TAB[n]. Chcemy uporządkować elementy zbioru X rosnąco, tzn. tak by TAB[i] < TAB[i+1] dla i=1,...n-1. Zauważmy, że wszystkie elementy w tablicy TAB mają różne wartości.

W przedstawionym algorytmie sortowanie zakładamy, że pq jest początkowo pustą kolejką priorytetową.

sortowanie (TAB : tablica){
	i :=1;
	while (i £ TAB.length) do	// elementy TAB[1]...,TAB[i-1] znajdują się w pq
	pq := insert(TAB[i], pq);	// TAB[1]...,TAB[i-1], TAB[i] są w kolejce pq
	i := i +1;	//TAB[1]...,TAB[i-1] znajdują się w pq
	od;
	i :=1;	//TAB[1] £ TAB[2]...£ TAB[i-1].
	while not empty(pq) do
	TAB[i] := min(pq);	// TAB[1] £ TAB[2]...£ TAB[i-1] £ TAB[i].
	pq := delmin(pq);
	i := i+1;	//TAB[1] £ TAB[2]...£ TAB[i-1]£ TAB[i]
	od;
}

Własność ta wynika z postulatu PQ3 i z założenia, że elementy zbioru X znajdują się w tablicy TAB.

Zajmijmy się bardziej szczegółowo drugą pętlą. Niezmiennikiem tej pętli jest formuła

TAB[1] £ TAB[2]...£ TAB[i-1] oraz {x : member(x,pq)} = X\{TAB[1],...,TAB[i-1]}.

Oczywiście przed wykonaniem drugiej pętli jest to formuła prawdziwa: i=1, zbór {TAB[1],...,TAB[i-1]} jest pusty, a kolejka pq zawiera wszystkie elementy zbioru X. Załóżmy, że formuła ta jest prawdziwa na początku itej iteracji.

Na mocy postulatu (PQ2), min(pq) jest najmniejszym elementem ze wszystkich, które należą do pq, czyli min(pq) £ x, dla x ÎX \ {TAB[1],...,TAB[i-1]} oraz TAB[j] £ min(pq) dla j < i. Zatem po wykonaniu przypisania TAB[i] := min(pq); mamy uporządkowany rosnąco ciąg TAB[1] £ TAB[2]...£ TAB[i]. Zgodnie z postulatem (PQ4), wykonanie instrukcji spowoduje, że element min(pq) nie będzie należał do kopca. Stąd {x : member(x,pq)} = X\{TAB[1],...,TAB[i]}. Po zmianie wartości licznika i, mamy znów prawdziwą formułę niezmiennika. Ponieważ po n krokach kolejka będzie pusta, a niezmiennik nadal spełniony, więc otrzymamy TAB[1] £ TAB[2]...£ TAB[n].

Dane są zbiory A, B, C w pewnej liniowo uporządkowanej przestrzeni < E, £ > takie, że para (A, B) stanowi podział zbioru C, tzn.

Znaleźć podział zbioru C na podzbiory A', B' takie, że |A'|= |A|, |B'| = |B| oraz wszystkie elementy zbioru A' poprzedzają wszystkie elementy zbioru B', tzn.

Idea rozwiązania polega na kolejnym porównywaniu elementu najmniejszego ze zbioru B z elementem największym w zbiorze A. Jeśli element najmniejszy w zbiorze B jest mniejszy niż element największy w zbiorze A, to powinien on się znajdować w zbiorze A. Jeśli natomiast najmniejszy element w B jest większy od największego elementu w A, to wszystkie elementy zbioru A są mniejsze od wszystkich elementów zbioru B, a więc osiągnęliśmy poszukiwany podział.

Niech A składa się z liczb 3, 15, 1, 9, 10, 4, 8, 5, a B z liczb 24, 17, 18, 12, 23. Moc zbioru wynikowego A' ma być taka sama jak moc zbioru A (i analogicznie dla B), przyjmijmy więc, że zarówno A jak i B są dwiema tablicami o ośmiu i pięciu elementach, odpowiednio. Kolejne stany obu tablic przedstawiono na rysunku 10.1. Po trzech zamianach elementów, najmniejszą liczbą w zbiorze B jest 15, a największą w A, 12. Wynika stąd, że wszystkie elementy zbioru A są mniejsze niż elementy zbioru B. J

Zwróćmy uwagę, że operacje jakie wykonujemy w tym algorytmie, to znajdywanie minimum, wstawianie i usuwanie elementu minimalnego ze względu na jakiś porządek. Taki zestaw operacji jest dostępny w każdej kolejce priorytetowej. Przyjmijmy więc, że strukturą danych dla naszego algorytmu jest kolejka priorytetowa. Użyjemy dwóch kolejek priorytetowych: jednej, uporządkowanej ze względu na porządek ³, do reprezentowania zbioru A i drugiej, uporządkowanej ze względu na porządek £, do reprezentowania zbioru B. Niech PQ_³ i PQ_£ będą dwoma typami kolejek priorytetowych. W ten sposób minimum w zbiorze A, to element największy tego zbioru w sensie relacji £. Operacja delmin, to operacja usuwania elementu największego w A. Specyfikację problemu rozdzielania zapiszmy jako parę <wp, wk>, gdzie

wk = {A' È B' = C, A' Ç B' = Æ, |A'| = n, |B'| = m, ("a Î A')("b Î B') a £ b}.

podziel(A: PQ_³, B: PQ_£){
	while (not min(A) £ min(B) ) do	// para (A,B) stanowi podział zbioru C
	a := min(A);
	b := min(B);
	A := delmin(A); A := insert(b,A);
	B := delmin(B); B := insert(a,B);
		// para (A,B) jest podziałem zbioru C
	od;
}

Niezmiennikiem pętli w tym algorytmie jest formuła |A| = n, |B| = m, A È B = C, A Ç B = Æ. Rzeczywiście, w każdej iteracji, po wykonaniu instrukcji "a := min(A);b := min(B);", na mocy założenia o rozłączności zbiorów A i B oraz własności operacji min w kolejce priorytetowej, mamy

Po wykonaniu operacji "A := delmin(A) ", prawdziwa jest formuła not member(a,A), czyli |{x: member(x,A)}|=n-1. Z kolei wykonanie operacji "A := insert(b,A);" zwiększyło liczbę elementów w A, bo na mocy postulatu (PQ3) mamy member(b,A). Zatem |{x: member(x,A)}|=n. Podobnie dla zbioru B. Suma zbiorów A i B jest stale taka sama: przekładamy tylko elementy z jednej kolejki do drugiej.

Skoro przed wykonaniem pętli był spełniony warunek początkowy i skoro jest on spełniony po wykonaniu każdej iteracji, to jest spełniony po wyjściu z pętli. Ponieważ wychodzimy z pętli tylko wtedy, gdy spełniony jest warunek min(A) £ min(B), tzn. gdy element największy w zbiorze A jest mniejszy od elementu najmniejszego w zbiorze B. Z własności porządku liniowego mamy więc ("a Î A')("b Î B') a £ b.

A jaka jest gwarancja, że po skończonej liczbie kroków rzeczywiście spełniony będzie warunek min(A) £ min(B)? Niech np. n<m i niech k będzie liczbą elementów zbioru A, które są większe od pewnych elementów zbioru B. Po każdej iteracji liczba k maleje o jeden: największy element jest usunięty i przeniesiony do zbioru B. Po dokładnie k krokach wszystkie elementy zbioru A są mniejsze od wszystkich elementów zbioru B, a wtedy min(A) £ min(B) i algorytm zatrzymuje się.

Koszt algorytmu zależy od przyjętej implementacji kolejki priorytetowej. Ogólnie, algorytm wykona 2 ´min{n,m}operacji delmin i insert.

Pytanie 2: Który z algorytmów sortowania: HeapSort, czy algorytm sortowanie, z kolejką priorytetową zaimplementowaną jako kopiec, ma mniejszy koszt, jeśli zastosowano je do tablicy o n elementach?


A:	17	15	1	9	10	3	8	23		B:	24	4	18	12	5

						23=	maxA	³	minB	=4

A:	17	15	1	9	10	3	8	4		B:	24	23	18	12	5

						17=	maxA	³	minB	=5

A:	5	15	1	9	10	3	8	4		B:	24	23	18	12	17

						15=	maxA	³	minB	=12

A:	5	12	1	9	10	3	8	4		B:	24	23	18	15	17

						12=	maxA	£	minB	=15

						Rysunek 10.1