1 Treści multimedialne - kodowanie, przetwarzanie, prezentacja Odtwarzanie treści multimedialnychAndrzej Majkowski informatyka +

2 Sortowanie przez wybieranie (selectionsort) Iwona i Ireneusz Bujnowscy

3 Wyszukiwanie minimalnego elementu w tablicySelectionSort emin - kandydat na element minimalny w tablicy t[n] Poniżej fragment kodu na znalezienie elementu najmniejszego w tablicy t[n]    emin = t[0]; for (int i=1; i      if (t[i]< emin) emin = t[i]; Dla i=0 sprawdzany jest warunek t[0]>t[i] jeżeli jest prawdziwy następuje zamiana elementów miejscami … Dla i=n-2 sprawdzamy warunek t[n-2]>t[n-1] i zamieniamy miejscami elementy jeżeli warunek jest prawdziwy

4 Wyszukiwanie minimalnego elementu w tablicySelectionSort Ten algorytm można nieco zmodyfikować: zamiast szukać najmniejszej wartości można po prostu pamiętać gdzie w tablicy taka wartość występuje:     pmin = 0; for (int i=1; i      if (t[i]< t[pmin]) pmin = i; pmin- indeks gdzie znajduje się element minimalny Zmienna pmin na początku działania algorytmu wskazuje na element spod indeksu 0, który jest z założenia kandydatem na element najmniejszy. W wierszach znajduje się pętla, w której sprawdzane są kolejne elementy i porównywane z elementem z pozycji pmin. Jeśli testowany element jest mniejszy, to od tego momentu zmienna pmin wskazuje na jego indeks

5 Sortowanie przez wybieranieSelectionSort Algorytm sortowania przez wybieranie można opisać przynajmniej na dwa sposoby: W wyniku działania algorytmu na kolejne i-te pozycje tablicy wybierane są najmniejsze elementy z pozycji od i do n-1. W sortowanej tablicy wyróżniamy dwie jej części – posortowaną lewą i nieposortowaną prawą. Początkowo lewa część jest pusta, lecz w kolejnym kroku jest powiększana o jeden element, najmniejszy wybrany spośród wszystkich elementów z nieposortowanej części tablicy.

6 Sortowanie przez wybieranieSelectionSort Algorytm sortowania przez wybieranie można przedstawić na przykładzie element najmniejszy 1 na właściwej pozycji element najmniejszy 2 (zamiana z 7) element najmniejszy 3 (zamiana z 8)

7 Sortowanie przez wybieranieSelectionSort Ciąg dalszy zamian-szukamy elementu najmniejszego na białym polu element najmniejszy 4 zamiana z 9 element najmniejszy 7 na właściwej pozycji element najmniejszy 8 (zamiana z 9) element ostatni 9 na właściwej pozycji

8 Sortowanie przez wybieranieSelectionSort Fragment kodu     for (int p=0; p {      pmin = p; for (int i=p+1; i      if (t[i]< t[pmin]) pmin = i; swap(t[i], t[pmin]) } Złożoność algorytmu sortowania przez wybieranie: O(n2)

9 Sortowanie przez wybieranieSelectionSort       Algorytm sortowania przez wybieranie zilustrowany tańcem:

10