I_P_W14_M10_C++ Sortowanie przez wybieranie w języku C++
Sortowanie przez wybieranie
Metoda sortowania przez wybieranie w porządku rosnącym polega na znalezieniu najmniejszego elementu zbioru i umieszczeniu go na pierwszym miejscu. Obiekt, który się tam wcześniej znajdował, trafia na miejsce zajmowane dotychczas przez element o najmniejszej wartości klucza.
Następnie wśród pozostałych (jeszcze nieposortowanych) elementów znowu wyszukuje się ten o najmniejszej wartości klucza i umieszcza go na drugim miejscu (ponownie dokonując zamiany z dotychczasowym obiektem) itd.
W każdym cyklu zmniejsza się liczba nieposortowanych elementów. Opisane czynności wykonuje się aż do momentu, w którym pozostanie tylko jeden element w części nieposortowanej – na pewno wartość jego klucza jest największa w całym zbiorze.
Kiedy sortujemy tablicę malejąco, rozpoczynamy od znalezienia elementu największego. Zamieniamy go miejscami z elementem, który znajdował się na pierwszej pozycji.
Kolorem zielonym zaznaczono miejsce przeznaczone dla pierwszego elementu. Ponieważ sortujemy zbiór malejąco, powinna się tu znaleźć największa liczba.
Jest nią zaznaczony kolorem czerwonym element o wartości 9. Zamieniamy go miejscami z będącą na pierwszej pozycji liczbą 5.
Na razie umieściliśmy jeden element we właściwym miejscu. Elementy już posortowane oznaczymy barwą żółtą. Teraz musimy znaleźć obiekt o największej wartości klucza w nieposortowanej części i zamienić go miejscami z liczbą 2 (pole to ma obecnie barwę zieloną).
Element o wartości 8 zamieniamy miejscami z liczbą 2. Rozpoczynamy szukanie wartości, która powinna znaleźć się na trzeciej pozycji.
Cały proces trwa aż do odnalezienia przedostatniego elementu. Ostatnia wartość na pewno jest najmniejsza:
