obrazek

Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych.
Autor artykułu: mgr Jerzy Wałaszek, wersja1.0

obrazek

Sortowanie przez wybór

Sortowanie (ang. sort) zbioru polega na wykonaniu takiej permutacji jego elementów, aby dla dowolnych dwóch elementów a_i i a_j należących do tego zbioru zachodziły poniższe warunki:

Zbiór uporządkowany niemalejąco:

obrazek

Zbiór uporządkowany nierosnąco:

obrazek

Permutację taką osiągamy, przestawiając odpowiednio elementy zbioru. Zatem algorytm sortujący zmienia kolejność elementów w zbiorze, jeśli nie spełniają one powyższych warunków. Przy opisie algorytmu zakładamy, iż chcemy uzyskać porządek niemalejący - kolejne elementy są albo coraz większe, albo równe.

Sortowanie przez wybór (ang. selection sort) polega na wyszukaniu w zbiorze pozycji elementu najmniejszego (lub, w innej wersji, elementu największego). Znaleziony element najmniejszy (w drugiej wersji największy) w zbiorze uporządkowanym powinien znaleźć się na samym początku (w drugiej wersji na samym końcu). Zatem wymieniamy element najmniejszy z pierwszym elementem zbioru. Do dalszych operacji zbiór pomniejszamy o pierwszy element, który już jest uporządkowany. Procedurę powtarzamy ponownie, znajdując drugi element najmniejszy. Element ten wymieniamy z elementem na pozycji drugiej. Procedurę kontynuujemy, aż zbiór będzie jednoelementowy. W wyniku otrzymujemy zbiór posortowany.

Algorytm sortowania przez wybór

Dane wejściowe:

n - liczba elementów
T[] - tablica n elementowa zawierająca elementy do posortowania. Elementy są numerowane od 0 do n-1.

Dane wyjściowe:

T[] - tablica z posortowanymi elementami

Dane pomocnicze:

i,j - indeksy elementów T[]
v_min - wartość minimalna
p_min - pozycja wartości minimalnej w zbiorze

Lista kroków:

Krok 1: Dla i = 0,1,...,n-2: wykonuj kroki 2...9
Krok 2:     v_min ← T[i]
Krok 3:     p_min ← i
Krok 4:     Dla j = i+1,i+2,...,n-1: wykonuj kroki 5...8
Krok 5:         Jeśli T[j] ≥ v_min, to następny obieg
Krok 6:         v_min ← T[j]
Krok 7:         p_min ← j
Krok 8:         Następny obieg
Krok 9:     T[i] ↔ T[p_min]
Krok 10: Zakończ

Przykładowe dane dla programu:

Pierwsza liczba n określa ilość elementów w zbiorze. Następne n liczb definiuje n kolejnych elementów. Liczby zbioru są rzeczywiste.

100
311.58 125.55 -378.83 222.614 192.78 281.21 499.2 -67.17 -190.11 -355.854
-452.88 -14.33 -290.82 -382.94 491.62 -114.23 43.68 -165.22 -57.14 451.944
-81.21 429.24 -104.91 147.35 64.24 -420.34 -405.92 -335.13 -307.073 57.658
63.37 -165.96 -322.86 612.46 -63.72 245.47 69.957 435.526 489.225 41.146
311.06 -361.61 369.82 496.097 333.34 248.82 -197.91 -452.55 34.52 370.28
59.767 -50.481 265.92 -35.345 14.21 -161.67 -498.86 -386.22 -124.5 -222.74
319.1 -307.25 -68.49 -489.31 196.34 171.28 -361.22 -493.12 171.47 -409.77
398.42 58.691 378.22 -95.74 297.55 -204.4 362.510 111.386 -220.78 45.943
-199.874 -20.92 410.52 387.28 -221.11 179.67 -323.87 -178.77 176.25 -31.21
-75.48 279.5 -334.4 439.25 -382.8 303.405 207.925 -60.527 -481.694 -40.104

Program sortowania zbioru

// Sortowanie przez wybór
// (C)2010 I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

int main()
{
    double * T,vmin,x;
    int i,j,n,pmin;

    // odczytujemy liczbę elementów

    cin >> n;

    // tworzymy tablicę dynamiczną o n elementach

    T = new double[n];

    // wczytujemy elementy do tablicy

    for(i = 0; i < n; i++) cin >> T[i];

    // sortujemy tablicę

    for(i = 0; i <= n-2; i++)
    {
        vmin = T[i];
        pmin = i;
        for(j = i + 1; j < n; j++)
            if(T[j] < vmin)
            {
                vmin = T[j];
                pmin = j;
            }
        x = T[i]; T[i] = T[pmin]; T[pmin] = x;
    }

    // wyświetlamy posortowaną tablicę

    cout << endl;

    for(i = 0; i < n; i++) cout << T[i] << " ";

    cout << endl;

    // usuwamy tablicę dynamiczną

    delete [] T;

    return 0;
}

Przerób program, tak aby sortował zbiór nierosnąco. Wypróbuj również drugą wersję, która sortuje zbiór od końca.

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe