Sortiranje selekcijom

Sortiranje selekcijom

Animacija Sortiranja selekcijom
Klasa	Algoritam za sortiranje
Struktura podataka	niz
Najgora performanca	O(n2)
Najgora prostorna kompleksnost	O(n)

Sortiranje selekcijom (engl. selection sort) je algoritam sortiranja koji se zasniva na principu grube sile. Ovaj algoritam još poznat i pod imenom metod selekcije. Kada kažemo gruba sila mislimo na obrađivanje svakog elementa posebno. Sortiranje selekcijom sortira niz elemenata tako što ga prvo celog pretraži, kako bi našao prvi podoban element (npr. najveći ili najmanji) i smestio ga na prvo mesto u nizu. Tada pretražuje celi ostatak niza (bez prvog mesta) kako bi našao drugi takav element i smestio na drugo mesto u nizu. Onda se postupak ponavlja za ostatak niza bez prvog i drugog mesta itd. Ovo mu donosi vremensku složenost O(n²). Količina korišćene memorije je O(1) ukoliko se izmene vrše na originalnom nizu, a O(n) ako se pravi sortirana kopija niza.

Sortiranje selekcijom može biti stabilno, ali i ne mora, zavisno od implementacije.

Primer

Primer sortiranja jednog niza selekcijom. Niz treba da se sortira u rastućem poretku.

2 5 11 8 7 9 1 15 16 4

Prvo se pretražuje celi niz, da bi se našao minimalan element, i to je 1. On zamenjuje svoje mesto sa elementom na prvom mestu u nizu. Nadalje će svi elementi koji su već na svom mestu biti u podebljanom zapisu:

1 5 11 8 7 9 2 15 16 4

Potom sledi traženje novog minimalnog elementa u preostalom delu niza, od broja 5 do broja 4. Taj element je 2 i on zamenjuje mesto sa drugim elementom u nizu:

1 2 11 8 7 9 5 15 16 4

Itd.

1 2 4 8 7 9 5 15 16 11
1 2 4 5 7 9 8 15 16 11
1 2 4 5 7 9 8 15 16 11
1 2 4 5 7 8 9 15 16 11
1 2 4 5 7 8 9 15 16 11
1 2 4 5 7 8 9 11 16 15
1 2 4 5 7 8 9 11 15 16
1 2 4 5 7 8 9 11 15 16

Implementacija u programskom jeziku C

void zameniMesta(int* niz, int i1, int i2)
{
  static int bafer;
  bafer = niz[i1];
  niz[i1] = niz[i2];
  niz[i2] = bafer;
}

void sortiranjeSelekcijom(int* niz, int n)
{
  int i, j;
  int najmanji, indeksNajmanjeg;
  
  // Пролазак кроз цели низ. У сваком кораку ће по
  // један елемент добити своје коначно место.
  for(i=0; i<n; i++)
  {
    najmanji = niz[i];
    indeksNajmanjeg = i;
    
    // Налажење најмањег
    for(j=i+1; j<n; j++)
    {
      // Ако је мањи од тренутно најмањег нађен...
      if(niz[j] < najmanji)
      {
        // ... запамтити га као новог најмањег.
        najmanji = niz[j];
        indeksNajmanjeg = j;
      }
    }

    // Ако најмањи није већ на свом месту,
    // поставити га тамо.
    if(indeksNajmanjeg != i)
    { zameniMesta(niz,i,indeksNajmanjeg); }
  }
}

Implementacija u programskom jeziku Python

import sys
A = [64, 25, 12, 22, 11]
 
# Petljom prolazimo kroz svaki element
for i in range(len(A)):
     
    # Pronadji minimalni element u nesortiranom nizu
    min_idx = i
    for j in range(i+1, len(A)):
        if A[min_idx] > A[j]:
            min_idx = j
             
    # Zameni minimum sa prvim elementrom         
    A[i], A[min_idx] = A[min_idx], A[i]
 
# Stampamo sortirani niz
print ("Sortiran niz")
for i in range(len(A)):
    print("%d" %A[i]),

Implementacija u programskom jeziku Java

    void sort(int arr[])
    {
        int n = arr.length;
 
        // Prolazimo kroz svaki element
        for (int i = 0; i < n-1; i++)
        {
            // Nalazimo minimalni element
            int min_idx = i;
            for (int j = i+1; j < n; j++)
                if (arr[j] < arr[min_idx])
                    min_idx = j;
 
            // Zameni pronadjeni minimum sa prvim elementom
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }

Implementacija algoritma u opadajućem obliku u programskom jeziku Java

    void sort(int arr[])
    {
        int n = arr.length;
 
        // Prolazimo kroz svaki element
        for (int i = 0; i < n-1; i++)
        {
            // Nalazimo maksimalni element
            int max_idx = i;
            for (int j = i+1; j < n; j++)
                if (arr[j] > arr[max_idx])
                    min_max = j;
 
            // Zameni pronadjeni maksimum sa prvim elementom
            int temp = arr[max_idx];
            arr[max_idx] = arr[i];
            arr[i] = temp;
        }
    }

Složenost

Efikasno sortiranje je važno za optimizaciju korišćenja drugih algoritama (kao što su algoritmi pretrage i spajanja) koje zahtevaju unos podataka u sortirane liste. U poređenju sa drugim algoritmima, kod sortiranja selekcijom nije teško ustanoviti kolika je složenost. Naime, imamo n elemenata i isto tako n-1 poređenja nakon čega ih dovodimo na prvo mesto. Pronalaženje sledećeg najmanjeg elementa zahteva pretraživanje n-1 itd. Time dobijamo formulu $(n-1)+(n-2)+...+1=\sum _{i=1}^{n-1}i=\sum _{i=1}^{n-1}{\binom {i}{1}}$

sledeće što treba da uradimo je da se setimo formule iz kombinatorike $k\in \mathbb {N} ,k\geqslant r$,

$\sum _{i=r}^{k}{i \choose r}={k+1 \choose r+1}$ - ovu formulu možemo dokazati indukcijom.

Kada primenimo ovu formulu dobijamo $\sum _{i=1}^{n-1}{\binom {i}{1}}={\binom {n}{2}}={\frac {n!}{2!(n-2)!}}={\frac {1}{2}}n(n-1)={\frac {1}{2}}(n^{2}-n)$

dobijamo vremensku složenost $O(n^{2})$ a pošto imamo n elemenata na ulazu prostorna složenost je $O(n)$

Poređenje sa drugim algoritmima za sortiranje

Sortiranje selekcijom je praktično jedini algoritam za sortiranje kod koga brzina sortiranja ne zavisi od početnog stanja niza. Dakle kod njega nema najbolji i najgori slučaj kao kod ostalih algoritama. Jednostavno - računar uvek prolazi kroz sve elemente niza tražeći minimume. Suštinska prednost algoritma je u tome što uvek ima samo N-1 zamenu, ali mana je što je broj upoređivanja ravan Bubble sortu. Kada imamo nizove velikih dimenzija, tu je sortiranje selekcijom totalno prevaziđeno od strane podeli pa vladaj (engl. divide and conquer) algoritama kao što je na primer merge sort. Složenost podeli pa vladaj algoritama je $O(nlog(n))$. Međutim, sortiranje selekcijom ili i insertion sort su daleko efikasniji za nizove malih dimenzija (nekih 10 - 20 elemenata). Insection sort je vrlo sličan sortiranju selekcijom po tome što nakon prvih k iteracija, prvih k elementa su sortirana. Njegova prednost je u tome što prolazi samo kroz one koje mora kako bi postavio k+1 element, dok sortiranje selekcijom mora da prođe kroz sve elemente kako bi pronašao k+1 element. Običnom računicom vidimo da će insertion sort imati duplo manje poređenja, ali isto tako ima primera gde i neće raditi brže od sortiranja selekcijom a to je recimo kad je niz obrnuto sortiran. Prednost sortiranja selekcijom u odnosu na insertion sort je u broju zamena ($O(n)$ naspram $O(n^{2})$ ).

Varijante

Heapsort značajno unapređuje klasičan algoritam korišćenjem hip struktura kako bi ubrzao proces pronalaženja i uklanjanja najmanjeg elementa. Ovo će nam omogućiti da pronalazimo sledeći najmanji element u složenosti Θ(log n) umesto Θ(n) u unutrašnjoj petlji našeg algoritma. Čime dobijamo da nam je vreme smanjeno na Θ(n log n).

Kontrola toka

U računarskoj nauci, analiza kontrole toka (engl. CFA - control flow analysis) je tehnika statičke analize kodova za kontrolisanje toka podataka kroz hardver. Kontrolni protok se izražava kao grafik upravljačkog protoka (engl. CFG - control flow graph).

Upravljanje tokom predstavlja redosled po kome se naredbe, uputstva ili pozivi funkcija proveravaju ili izvršavaju. Eksplicitnim naglaskom na kontrolu toka se razlikuju imperativni programski jezici od deklarativnih programskih jezika.

U okviru imperativnog programskog jezika, naredba upravljanja tokom svojim izvršavanjem daje odgovor na pitanje kojim putem (ako postoje 2 ili više) treba nastaviti izvršavanje. Kod ne-striktnih programskih jezika, funkcijama i jezičkim konstrukcijama se dolazi do istog rezultata, ali se to ne zove nužno upravljanje tokom.

Vrste naredbi kontrole tokom koje podržavaju različiti jezici se razlikuju, ali se mogu podeliti po njihovom efektu:

• nastavak na drugoj naredbi
  (bezuslovno grananje ili skok),
• izvršavanje bloka naredbi samo ako je ispunjen određeni uslov (izbor, odnosno uslovna grana),
• izvršavanje sklopa naredbi nijednom ili više puta, dok se ne ispuni određeni uslov (npr. petlja - isto gao i uslovna grana),
• izvršavanje udaljenog kompleta naredbi, nakon kojeg se uglavnom tok upravljanja vraća (potprogrami, koprogrami i kontinuacije),
• zaustavljanje programa, sprečavajući dalji rad (bezuslovni zastoj).

Skup naredbi je zato generalno strukturiran kao blok, koji pored grupisanja definiše i leksički obim.

Prekidi i signali su mehanizmi niskog nivoa koji menjaju tok upravljanja na sličan način kao i potprogrami, ali se pre javljaju kao odgovor na neke eksterne stimuluse (koji mogu da se dese asinhrono), nego na „in-lajn naredbe upravljanja tokom.

Reference

• Knuth, Donald (1997). The Art of Computer Programming. Volume 3: Sorting and Searching, Third Edition. Addison–Wesley. ISBN 978-0-201-89685-5.  Pages 138–141 of Section 5.2.3: Sorting by Selection.
• Levitin, Anany (2007). Introduction to the Design & Analysis of Algorithms. 2nd Edition. ISBN 978-0-321-35828-8.  Section 3.1: Selection Sort. pp. 98–100.
• Robert Sedgewick (1998). Algorithms in C++, Parts 1–4: Fundamentals, Data Structure, Sorting, Searching: Fundamentals, Data Structures, Sorting, Searching Pts. 1–4. Second Edition. Addison–Wesley Longman. ISBN 978-0-201-35088-3.  Pages 273–274