Сортирање селекцијом

Сортирање селекцијом
	Анимација Сортирања селекцијом
Класа	Алгоритам за сортирање
Структура података	низ
Најгора перформанца	О(n2)
Најгора просторна комплексност	О(n)

Сортирање селекцијом (енгл. selection sort) је алгоритам сортирања који се заснива на принципу грубе силе. Овај алгоритам још познат и под именом метод селекције. Када кажемо груба сила мислимо на обрађивање сваког елемента посебно. Сортирање селекцијом сортира низ елемената тако што га прво целог претражи, како би нашао први подобан елемент (нпр. највећи или најмањи) и сместио га на прво место у низу. Тада претражује цели остатак низа (без првог места) како би нашао други такав елемент и сместио на друго место у низу. Онда се поступак понавља за остатак низа без првог и другог места итд. Ово му доноси временску сложеност O(n²). Количина коришћене меморије је O(1) уколико се измене врше на оригиналном низу, а O(n) ако се прави сортирана копија низа.

Сортирање селекцијом може бити стабилно, али и не мора, зависно од имплементације.

Пример уреди

Пример сортирања једног низа селекцијом. Низ треба да се сортира у растућем поретку.

2 5 11 8 7 9 1 15 16 4

Прво се претражује цели низ, да би се нашао минималан елемент, и то је 1. Он замењује своје место са елементом на првом месту у низу. Надаље ће сви елементи који су већ на свом месту бити у подебљаном запису:

1 5 11 8 7 9 2 15 16 4

Потом следи тражење новог минималног елемента у преосталом делу низа, од броја 5 до броја 4. Тај елемент је 2 и он замењује место са другим елементом у низу:

1 2 11 8 7 9 5 15 16 4

Итд.

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

Имплементација у програмском језику 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); }
  }
}

Имплементација у програмском језику 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]),

Имплементација у програмском језику 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;
        }
    }

Имплементација алгоритма у опадајућем облику у програмском језику 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;
        }
    }

Сложеност уреди

Ефикасно сортирање је важно за оптимизацију коришћења других алгоритама (као што су алгоритми претраге и спајања) које захтевају унос података у сортиране листе. У поређењу са другим алгоритмима, код сортирања селекцијом није тешко установити колика је сложеност. Наиме, имамо n елемената и исто тако n-1 поређења након чега их доводимо на прво место. Проналажење следећег најмањег елемента захтева претраживање n-1 итд. Тиме добијамо формулу $(n-1)+(n-2)+...+1=\sum _{i=1}^{n-1}i=\sum _{i=1}^{n-1}{\binom {i}{1}}$

следеће што треба да урадимо је да се сетимо формуле из комбинаторике $k\in \mathbb {N} ,k\geqslant r$ ,

\sum _{i=r}^{k}{i \choose r}={k+1 \choose r+1}

- ову формулу можемо доказати индукцијом.

Када применимо ову формулу добијамо $\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)$

добијамо временску сложеност $O(n^{2})$ а пошто имамо n елемената на улазу просторна сложеност је $O(n)$

Поређење са другим алгоритмима за сортирање уреди

Сортирање селекцијом је практично једини алгоритам за сортирање код кога брзина сортирања не зависи од почетног стања низа. Дакле код њега нема најбољи и најгори случај као код осталих алгоритама. Једноставно - рачунар увек пролази кроз све елементе низа тражећи минимуме. Суштинска предност алгоритма је у томе што увек има само N-1 замену, али мана је што је број упоређивања раван Bubble sortu. Када имамо низове великих димензија, ту је сортирање селекцијом тотално превазиђено од стране подели па владај (енгл. divide and conquer) алгоритама као што је на пример merge sort. Сложеност подели па владај алгоритама је $O(nlog(n))$ . Међутим, сортирање селекцијом или и insertion sort су далеко ефикаснији за низове малих димензија (неких 10 - 20 елемената). Insection sort је врло сличан сортирању селекцијом по томе што након првих к итерација, првих к елемента су сортирана. Његова предност је у томе што пролази само кроз оне које мора како би поставио к+1 елемент, док сортирање селекцијом мора да прође кроз све елементе како би пронашао к+1 елемент. Обичном рачуницом видимо да ће insertion sort имати дупло мање поређења, али исто тако има примера где и неће радити брже од сортирања селекцијом а то је рецимо кад је низ обрнуто сортиран. Предност сортирања селекцијом у односу на insertion sort је у броју замена ( $O(n)$ наспрам $O(n^{2})$ ).

Варијанте уреди

Heapsort значајно унапређује класичан алгоритам коришћењем хип структура како би убрзао процес проналажења и уклањања најмањег елемента. Ово ће нам омогућити да проналазимо следећи најмањи елемент у сложености Θ(log n) уместо Θ(n) у унутрашњој петљи нашег алгоритма. Чиме добијамо да нам је време смањено на Θ(n log n).

Контрола тока уреди

У рачунарској науци, анализа контроле тока (енгл. CFA - control flow analysis) је техника статичке анализе кодова за контролисање тока података кроз хардвер. Контролни проток се изражава као график управљачког протока (енгл. CFG - control flow graph).

Управљање током представља редослед по коме се наредбе, упутства или позиви функција проверавају или извршавају. Експлицитним нагласком на контролу тока се разликују императивни програмски језици од декларативних програмских језика.

У оквиру императивног програмског језика, наредба управљања током својим извршавањем даје одговор на питање којим путем (ако постоје 2 или више) треба наставити извршавање. Код не-стриктних програмских језика, функцијама и језичким конструкцијама се долази до истог резултата, али се то не зове нужно управљање током.

Врсте наредби контроле током које подржавају различити језици се разликују, али се могу поделити по њиховом ефекту:

наставак на другој наредби
(безусловно гранање или скок),
извршавање блока наредби само ако је испуњен одређени услов (избор, односно условна грана),
извршавање склопа наредби ниједном или више пута, док се не испуни одређени услов (нпр. петља - исто гао и условна грана),
извршавање удаљеног комплета наредби, након којег се углавном ток управљања враћа (потпрограми, копрограми и континуације),
заустављање програма, спречавајући даљи рад (безусловни застој).

Скуп наредби је зато генерално структуриран као блок, који поред груписања дефинише и лексички обим.

Прекиди и сигнали су механизми ниског нивоа који мењају ток управљања на сличан начин као и потпрограми, али се пре јављају као одговор на неке екстерне стимулусе (који могу да се десе асинхроно), него на „ин-лајн наредбе управљања током.

Референце уреди

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