Problem sortowania możemy zdefiniować następująco: Dany jest skończony ciąg e₁, ..., e_n elementów pewnego zbioru liniowo uporządkowanego (E, £). Znaleźć taką permutację i₁, ..., i_n liczb 1,..., n, że e_i1 £ ... £ e_in.

Jeżeli elementami ciągu e są liczby 6,2,8,9,1, to szukaną permutacją jest 5,2,1,3,4. Rzeczywiście, piąty element jest najmniejszym elementem tego ciągu, a czwarty jest elementem największym. Ustawiając elementy w kolejności: najpierw piąty, potem drugi, pierwszy, trzeci i czwarty, ustawimy wszystkie elementy danego ciągu w porządku niemalejącym. J

W tym i w następnych punktach tego wykładu, będziemy poszukiwać takich algorytmów rozwiązywania problemu sortowania, które używają tylko operacji porównywania elementów (mówimy, że sortują w modelu drzew decyzyjnych (por. wykład II, p.5). We wszystkich przedstawionych algorytmach zakładać będziemy, że ciąg jest reprezentowany przez tablicę e o elementach e[1],..., e[n]. Ponadto, zamiast szukać odpowiedniej permutacji indeksów ciągu, będziemy dokonywać bezpośredniej permutacji elementów, tak by po zakończeniu algorytmu, zawartością tablicy e był ciąg uporządkowany niemalejąco.

Specyfikację zadania sortowania ciągu e₁, ..., e_n scharakteryzujemy następującymi warunkami:

wk = {e[1] £ e[2] £ ... £ e[n] oraz istnieje taka permutacja i₁, ..., i_n liczb 1,..., n,e[1] = e_i1, e[n]= e_in }.

Warunek początkowy stwierdza tylko, że ciąg, który chcemy posortować jest niepusty, a jego elementy zostały umieszczone w tablicy e. Warunek końcowy natomiast stwierdza, że wartości tablicy e (po wykonaniu algorytmu) tworzą ciąg uporządkowany niemalejąco i wartości te są permutacją elementów danego ciągu e₁, ..., e_n.

Najprostszym algorytmem sortowania jest algorytm sortowania przez wybór (inaczej "przez selekcję"). Wymaga on wielokrotnego wyszukiwania elementu minimalnego. Aby nie powtarzać kodów już omówionych algorytmów, założymy, że min(e,i,j) jest optymalnym algorytmem, który dla dowolnej tablicy e i dowolnych liczb i, j £ n, znajduje pozycję najmniejszego elementu w ciągu e[i], e[i+1], ... , e[j], a swap(e[i], e[j]) jest procedurą, która dokonuje zamiany miejscami elementów i-tego i j-tego tablicy e.

Idea tego algorytmu polega na sukcesywnym wybieraniu elementu najmniejszego z tych, które znajdują się w jeszcze nieuporządkowanej części tablicy. Dokładniej, sortowanie odbywać się będzie w n-1 etapach. W i-tym etapie i-1 pierwszych pozycji tworzy już ciąg uporządkowany. Znajdujemy pozycję, na której znajduje się element najmniejszy wśród elementów e[i],...,e[n], a następnie umieszczamy go na i-tej pozycji w tablicy, rozszerzając w ten sposób już uporządkowany fragment.

Niech dany ciąg składa się z liczb całkowitych, 4,2,6,1,7,5. Kolejne stany tablicy e w trakcie wykonywania algorytmu są następujące:

Elementy, które zamieniły się miejscami zostały zaznaczone tłustą czcionką. J

Algorytm sortowania przez wybór zapiszemy w postaci procedury SelectionSort z jednym parametrem formalnym typu "ciąg". Zakładamy, że obiekty tego abstrakcyjnego typu mają określony atrybut lenght, który mówi o liczbie elementów ciągu.

SelectionSort (e : ciąg){
	i := 1; n := e.length;
	while (i < n) do	// e[1] £...£ e[i-1], i £ n oraz e[i-1] £ {e[i],...,e[n]}
	j := min(e, i, n);	// j jest pozycją elementu najmniejszego wśród e[i],...,e[n]
	swap(e[j], e[i]);	// e[1] £ ... £ e[i-1] £ e[i] oraz e[i] £ {e[i+1],...,e[n]}
	i := i + 1;	// e[1] £ ... £ e[i-1] oraz e[i-1] £ {e[i],...,e[n]}
	od;	// e[1] £ ... £ e[i-1], i = n oraz e[i-1] £ e[n]
}

Analiza poprawności. Na rysunku 4_1 przedstawiliśmy sytuację w naszym ciągu na początku i-tej iteracji:

Uzasadnienie poprawności tego algorytmu jest bardzo proste. Niech przy wejściu do pętli będą spełnione własności

i < n+1, e[1] £...£ e[i-1], e[i-1] £ e[k] dla wszystkich k, takich że i £ k £ n. (*)

Dodatkowo wiemy, że spełniony jest test (i < n), tzn. i+1< n+1. Po wykonaniu instrukcji "j := min(e,i,n);" nie zmieniła się wartość żadnego parametru z wyjątkiem j, dla którego (na mocy założenia o poprawności algorytmu min) e[j] £ e[k] dla i £ k£ n. Po wykonaniu zamiany pozycji itej i jtej (swap(e[j],e[i])), wiemy, że

i+1 < n+1 oraz e[1] £...£ e[i], e[i] £ e[k] dla wszystkich k, takich że i £ k£ n.

Wykonanie instrukcji "i := i+1", spowoduje, że znów prawdziwa będzie formuła (*). Zatem znaleźliśmy niezmiennik pętli. Ponieważ przed pierwszym wejściem do pętli, własności (*) są trywialnie spełnione, więc, gdy po n-1 krokach, nie będzie już spełniony warunek i<n, znów spełnione będą warunki (*). Co więcej, wartością zmiennej i jest wtedy n, czyli

Ponadto, dla każdego i istnieje dokładnie jedna liczba naturalna j niewiększa od n, dla której e[i] = e _j algorutmu.(jest to pozycja, na której znaleźliśmy element minimalny w i-tym kroku. To dowodzi całkowitej poprawności algorytmu SelectionSort względem przyjętej specyfikacji.

Zauważmy jeszcze, że żadne szczególne cechy struktury danych nie były tu wykorzystywane, poza założeniem, że relacja £ jest porządkiem liniowym. Zatem prawdziwe jest twierdzenie:

Twierdzenie 1.1 Dla dowolnego niepustego ciągu, o elementach należących do dowolnej struktury danych, w której jest określony liniowy porządek, algorytm SelectioSort zatrzymuje się, a otrzymany wynik spełnia warunek końcowy

wk ={e[1] £...£ e[n-1]£ e[n]}.

Analiza kosztu: Koszt tego algorytmu mierzymy liczbą wykonanych porównań. Są one wykonywane w treści funkcji min. Ponieważ i zmienia się od 1 do n-1, zatem w kolejnych iteracjach szukamy minimum w coraz krótszych fragmentach ciągu. Zgodnie z przeprowadzoną wcześniej dyskusją kosztu algorytmu min, wyszukanie pozycji, na której znajduje się element minimalny w ciągu n-(i-1) elementowym wymaga dokładnie n-i porównań. Liczba wykonanych porównań jest sumą kolejnych liczb naturalnych od n-1 do 1.

Funkcja ta jest niestety kwadratowa, asymptotycznie dąży do nieskończoności tak jak funkcja n².

Dużo lepiej wypadnie koszt jeśli mierzyć go będziemy liczbą wykonanych operacji "swap". Ponieważ w każdej iteracji pętli "while (i<n)" wykonujemy tylko jedną taką operację, zatem wykonamy ich łącznie n-1. Koszt mierzony liczbą operacji swap jest więc liniowy.

Zauważmy jeszcze, że liczba wykonanych porównań nie zależy ani od wartości elementów, ani od kolejności w jakiej elementy występują w danym ciągu.

Algorytm sortowania przez wybór sortuje w miejscu, tzn. wykorzystuje tylko pamięć konieczną do przechowywania danych i kilka zmiennych pomocniczych. Jego koszt pamięciowy jest więc liniowy w stosunku do rozmiaru danych, S(SelectionSort,n) = Q(n)

Pytanie 1: W pewnej implementacji algorytmu SelectionSort, wszystkie wykonywane porównania zostały zilustrowane graficznie. Porównywane elementy są przez 30 milisekund wyświetlane na ekranie, innym, niż pozostałe elementy ciągu, kolorem. Ile czasu zajmie nam oglądanie wykonania tego algorytmu dla n=200?