Sortowanie przez wybór
Sortowanie przez wybór jest metodą najprostszą z sortowania. W tablicy należy znaleźć najmniejszy element i zamienić go miejscem z pierwszym elementem tablicy. Jeżeli najmniejszy element występuje wielokrotnie to trzeba wziąć pod uwagę ten, który znajduje się najbliżej początku tablicy.
Następnie we fragmencie tablicy, który obejmuje elementy od drugiego do ostatniego poszukiwane jest minimum i należy zamienić je miejscem z drugim elementem tablicy. Należy tak postępować dodając za każdym razem element do posortowanej części aż nastąpi ostatni element tablicy.
Podany problem sortowania przez wybór można przedstawić w kilku rozwiązaniach. Zaczynamy od specyfikacji problemu, która wyjaśni, jakie dane mamy, jakich potrzebujemy oraz jakich pomocniczych zmiennych będziemy używać.
Specyfikacja problemu sortowania przez wybór.
Lista kroków przedstawiająca rozwiązanie algorytmu sortowania przez wybór.
Schemat blokowy zawierający algorytm sortowania przez wybór.
Schemat blokowy zawiera dwie pętle sterujące wartościami i oraz j. Zewnętrzna steruje wartością zmiennej j, która wyznacza elementy zbioru od 1 do k-1. Algorytm ustawia element najmniejszy jako pierwszy element zbioru. Druga pętla (wewnętrzna) steruje zmienną i oraz porównuje resztę elementów z wartością minimalną. Pętla będzie sprawdzać czy element zbioru t[i] jest mniejszy od elementu t[pmin]. Jeżeli tak to znaleziony został nowy element minimalny. Kiedy pętla wewnętrzna zakończy swoje działanie wartość pmin będzie zawierać indeks elementu minimalnego. Następnie algorytm zamieni miejscami element t[j] z t[pmin], dzięki temu element minimalny znajdzie się w tej pozycji, której powinien. Zwiększając wartość j algorytm przechodzi do następnego elementu zbioru, wykonuje pętlę zewnętrzną.
Program sortujący dane zawarte w tablicy 10-cio elementowej metodą przez wybór.
0 komentarze