Sortowanie przez
wybór (selekcję)
Wykład: implementacja w C++, animacja pokazująca
sortowanie przez wybór (selekcję), złożoność algorytmu
SORTOWANIE PRZEZ
SELEKCJ (WYBIERANIE)
ALGORYTM SORTOWANIA PRZEZ
SELEKCJ (WYBIERANIE)
Sortowanie to polega na iteracyjnym znajdowaniu
najmniejszego (w sortowaniu rosnącym) lub największego
(w sortowaniu malejącym) elementu i zamianie go z
pierwszym elementem w tablicy, po czym rozmiar tablicy
zmniejszamy o jeden.
2
Złożoność czasowa tego algorytmu: O (n )
ALGORYTM SORTOWANIA PRZEZ
SELEKCJ (WYBIERANIE)
ALGORYTM:
a) wyznaczyć najmniejszy element w tablicy [0..n],
b) zamienić go miejscami z zerowym elementem tablicy,
c) wyznaczyć najmniejszy element w tablicy [1..n],
d) zamienić go miejscami z pierwszym elementem tablicy,
itd. aż do posortowania całej tablicy J
IMPLEMENTACJA W C++
void sortowanie_przez_selekcje(int *tab, int n)
{
int min,bufor;
for (int i=0; i
{
min=i;
//znajdowanie minimum
for (int j=i+1; j{
if (tab[j]min=j;
}
//zamiana
bufor=tab[min];
tab[min]=tab[i];
tab[i]=bufor;
}
}
PRZYKAAD SORTOWANIA
PRZEZ SELEKCJ
Dana jest tablica, którą należy posortować rosnąco:
9 2 6 5 1 3
0 1 2 3 4 5
indeks
PRZYKAAD SORTOWANIA
PRZEZ SELEKCJ
ITERACJA 1 ą MINIMUM = 1 musi znalezć się w szufladce
oznaczonej numerem 0 (następuje zamiana):
9 2 6 5 1 3
0 1 2 3 4 5
indeks
PRZYKAAD SORTOWANIA
PRZEZ SELEKCJ
ITERACJA 1 ą MINIMUM = 1 musi znalezć się w szufladce
oznaczonej numerem 0:
1 2 6 5 9 3
0 1 2 3 4 5
indeks
PRZYKAAD SORTOWANIA
PRZEZ SELEKCJ
ITERACJA 2 ą MINIMUM = 2 musi znalezć się w szufladce
oznaczonej numerem 1 (zdarzyło się, że już tam jest, więc
nie ma potrzeby zamiany):
1 2 6 5 9 3
0 1 2 3 4 5
indeks
PRZYKAAD SORTOWANIA
PRZEZ SELEKCJ
ITERACJA 3 ą MINIMUM = 3 musi znalezć się w szufladce
oznaczonej numerem 2 (następuje zamiana):
1 2 6 5 9 3
0 1 2 3 4 5
indeks
PRZYKAAD SORTOWANIA
PRZEZ SELEKCJ
ITERACJA 3 ą MINIMUM = 3 musi znalezć się w szufladce
oznaczonej numerem 2:
1 2 3 5 9 6
0 1 2 3 4 5
indeks
PRZYKAAD SORTOWANIA
PRZEZ SELEKCJ
ITERACJA 4 ą MINIMUM = 5 musi znalezć się w szufladce
oznaczonej numerem 3 (zdarzyło się, że już tam jest, więc
nie ma potrzeby zamiany):
1 2 3 5 9 6
0 1 2 3 4 5
indeks
PRZYKAAD SORTOWANIA
PRZEZ SELEKCJ
ITERACJA 5 ą MINIMUM = 6 musi znalezć się w szufladce
oznaczonej numerem 4 (następuje zamiana):
1 2 3 5 9 6
0 1 2 3 4 5
indeks
PRZYKAAD SORTOWANIA
PRZEZ SELEKCJ
ITERACJA 5 ą MINIMUM = 6 musi znalezć się w szufladce
oznaczonej numerem 4:
1 2 3 5 6 9
0 1 2 3 4 5
indeks
Wyszukiwarka
Podobne podstrony:
29 W rok przez Biblię Listy Piotra
Sortowanie przez wstawienie
sortowanie przez wstawianie
sortowanie przez wstawianie binarne
MIKROEKONOMIA WYKŁAD 3 (29 10 2011) Wybór między czasem wolnym a konsumpcją
Sortowanie przez zliczanie
04 29 Styczeń 1997 Maschadow to najlepszy wybór
Wybór znieczulenia do porodu przez cięcie cesarskie
Wybor firmy zarzadzajacej przez wspolnote mieszkaniowa
404 (B2007) Wybór biegłego rewidenta jedynie przez uprawniony organ
99 ROZ jakość wody do spożycia przez ludzi [M Z ][29 03 2
próbna 29 marca 2014
000805 29
więcej podobnych podstron