Algoritmi → Sortiranje → Sortiranje nizova: izbor, umetanje i mehurić

Sortiranje nizova: izbor, umetanje i mehurić

Zašto sortiramo?

Sortiran niz je mnogo lakše pretraživati i obrađivati: najmanji i najveći element su na krajevima, jednaki elementi su jedan do drugog, a traženi broj može da se nađe binarnom pretragom u nekoliko koraka umesto prolaskom kroz ceo niz.

Ako u nizu ima jednakih elemenata, umesto „rastuće“ tačnije je reći neopadajuće (svaki sledeći je veći ili jednak prethodnom). Na primer, niz 2 5 5 8 je sortiran neopadajuće.

Sortiranje izborom (selection sort)

Ideja: pronađi najmanji element i zameni ga sa prvim. Zatim u ostatku niza (od drugog elementa) pronađi najmanji i zameni ga sa drugim, i tako dalje. Posle koraka i prvih i + 1 elemenata je na svom konačnom mestu.

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[1000];
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 0; i < n - 1; i++) {
        int minPoz = i;                       // pozicija najmanjeg u delu a[i..n-1]
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[minPoz]) minPoz = j;
        swap(a[i], a[minPoz]);                // najmanji ide na mesto i
    }

    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

Za opadajući poredak dovoljno je tražiti najveći umesto najmanjeg: if (a[j] > a[maxPoz]).

Sortiranje umetanjem (insertion sort)

Ideja: kao kada slažeš karte u ruci. Levi deo niza je već sortiran. Uzimaš sledeći element, pomeraš udesno sve veće elemente iz sortiranog dela i ubacuješ ga na oslobođeno mesto.

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[1000];
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 1; i < n; i++) {
        int x = a[i];                 // element koji umećemo
        int j = i - 1;
        while (j >= 0 && a[j] > x) {  // pomeramo veće elemente za jedno mesto udesno
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = x;                 // x ide na oslobođeno mesto
    }

    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

Sortiranje umetanjem je vrlo brzo kada je niz skoro sortiran: tada se elementi skoro ne pomeraju.

Metoda mehurića (bubble sort)

Ideja: prolazimo kroz niz i poredimo susedne elemente; ako su u pogrešnom redosledu, menjamo im mesta. Posle prvog prolaza najveći element „ispliva“ na kraj niza, kao mehurić. Ako u nekom prolazu nije bilo nijedne zamene, niz je sortiran i možemo da stanemo.

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[1000];
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int prolaz = 0; prolaz < n - 1; prolaz++) {
        bool bilo = false;                         // da li je bilo zamena u ovom prolazu
        for (int j = 0; j < n - 1 - prolaz; j++) { // poslednjih "prolaz" elemenata je već na mestu
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                bilo = true;
            }
        }
        if (!bilo) break;                          // niz je već sortiran
    }

    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

Poređenje i složenost

Sva tri algoritma imaju dve ugnježdene petlje, pa za niz od n elemenata rade oko n²/2 poređenja. Kažemo da im je složenost O(n²) (čita se „o od n na kvadrat“).

Stabilan algoritam ne menja međusobni redosled jednakih elemenata – to je važno kada sortiramo, na primer, učenike po bodovima, a želimo da učenici sa istim brojem bodova ostanu po redosledu prijave.

Za veće nizove koriste se efikasni algoritmi složenosti O(n log n): sortiranje objedinjavanjem i brzo sortiranje. Na takmičenjima se u praksi koristi gotova funkcija sort.

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

Proveri znanje