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

Из Википедије, слободне енциклопедије
Сортирање селекцијом
Намена сортирање
Структура података низ
Временска компл. O(n²)
Меморијска компл. O(1)

Сортирање селекцијом (енгл. 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); }
  }
}