Algorytm bąbelkowy

Ciąg jest uporządkowany rosnąco, jeśli dla każego i>1 zachodzi: x[i]>=x[i-1]. Przestawiając sąsiednie wyrazy ciągu kolejno dla i=2,3,...,n spełniające nierówność x[i]<x[i-1] spowodujemy umieszczenie największego wyrazu ciągu na pozycji ostatniej. Podobną serię przestawień możemy zastosować do ciągu pomniejszonego o wyraz ostatni. W ten sposób dwa ostatnie wyrazy ciągu będą już na właściwych pozycjach. Kontynujując takie serie przestawień dla coraz mniejszych ciągów doprowadzimy w końcu do uporządkowania wszystkich wyrazów ciągu {x[i]}. Metoda ta jest zalecana do sprawdzania czy ciąg jest uporządkowany oraz poprządkowania ciągu, jeśli spodziewany się niewielkiej liczby przestawień, tj. gdy uporządkowanie ciągu zostało zakłócone tylko na kilku pozycjach.

Przykład:

Po k przebiegach ostanie k pozycji zajmować muszą właściwe wyrazy ciągu (wytłuszczone). Pozycje poprzedzające niekoniecznie musiały być już uporządkowane.

Dla i=2,3.,..,n wykonujemy następujące operację. Jeżeli istnieją j, 1<=j<i, takie, że element x[i]<x[j], to element x[i] zapamiętujemy, elementy x[j], j=j₀, j₀+1,...,i-1, przesuwamy o jedna pozycję w prawo, a następnie wstawiamy x[i] na miejsce x[j₀], gdzie j0 jest najmniejszym z indeksów j spełniającym ww. warunki. W przypadku, gdy nie ma indeksów j spełniających ww. warunki, czyli x[i] jest wieksze od każdego poprzednika, to nie wykonujemy żadnej operacji. Dla ciągów o długości mniejszej niz 9 elementów jest to algorytm najszybszy.

Przykład:

Dla każdego i=1,2,...,n-1 wykonujemy następującą operację: spośród wyrazów ciągu {x[i]} znajdujących się na pozycjach wyższych niż i-1 wybieramy wyraz najmniejszy, który znajduje się na pozycji j, a następnie zamieniamy pozycje wyrazów x[i] i x[j]. Algorytm ten jest zalecany, gdy interesuje nas wybór tylko kilku najmniejszych elementów ciągu, a nie uporząkowanie wszystkich jego wyrazów.

Przykład:

Idea tego algorytmu polega na podziale całego sortowanego ciagu na dwa podciągi. Po podziale powinniśmy zająć się ciągiem krótszym, a to z tego względu, aby na stosie gromadzic jak najmniej podzadań. Dla objasnienia zasady działania tego algorytmu przyjmujemy, że jako element podziału wybieramy zawsze lewy skrajny wyraz sortowanego ciągu (podciągu). W podanym niżej przykładzie jest nim x[1]=6. Chcemy tak poprzestawiać elementy ciągu, aby na lewo od 6 znajdowały się mniejsze wyrazy ciągu, a na prawo większe. Idąc od prawej strony szukamy elementu mniejszego od 6, a gdy go znajdziemy, to zamieniamy go z 6. Następnie idziemy od lewej strony i szukamy pierwszego większego elementu od 6, a po znalezieniu go również zamieniamy go z 6. Kontynuujemy takie postępowanie idąc raz z prawej a raz z lewej strony. Idąc od prwej strony zmniejszamy pewien indeks i, a od lewej zwiększamy pewien indeks j. Na początku i>j. Podział ciagu zostaje dokonany, gdy i<=j. Dla przejrzystości pierwszy element podziału zaznaczyliśmy czcionką pogrubioną, następne podkreśleniem.

Algorytm ten łatwiej jest zaprogramować rekursywnie w stylu:

		Procedure QuickSort(il,ir,x);
		{deklaracje}
		Begin
	     	{Instrukcje dzielące ciąg fragment <il,ir> ciągu od indeksu il do ir 
			 na dwie części <il,i> oraz <j,ir>}; 
	    	If i-il<ir-j then QuickSort(il,i,x)
	                     else QuickSort(j,ir,x)	 
		End;
	

Zwykły, nierekursywny styl programu znacznie przyspieszy działanie algorytmu. Innym łatwym sposobem przyspieszenia algorytmu jest sortowanie krótkich ciagów, które zostaną wygenerowane w trakcie QuickSort, algoprytmem karcianym. Najgorszy przypadek dla tego algorytmu, to ciąg już uporządkowany. Wtedy lepiej nie wybierać do podziału lewych skrajnych elementów jak to uczyniliśmy w przykładzie, a brać do tego ceclu element środkowy, np. x[(il+ir) div 2].

Przykład:

Podany algorytm można łatwo zmodyfikowac do szybkiego szukania mediany ciągu, bez zupelnego sortowania go. Jeżeli długość ciągu jest nieparzysta, to pozycją medialną jest (n+1)/2. A zatem w QuickSort wystraczy zajmowac się tylko tymi podciągami, które ta pozycje medialną zawierają. Tzn. dzielimy tylko te fragmenty <il,ir> ciągu dla których il<=(n+1)/2<=ir. W przypadku, gdy dlugość n ciągu jest parzysta mamy dwie pozycje medialne: n/2 oraz (n/2)+1. Średnia z x[n/2] i x[(n/2)+1] dla ciągu uporządkowanego jest medianą. Wystraczy więc zajmowac się tylko tymi fragmentami ciągu, ktore zawieraja jedna z dwu ww. pozycji medialnych.