Skip to content

Сортирање избором

Опис алгоритма

Идеја је да је да се сортирани низ формира тако што се за сваки индекс ind, прво пронађе индекс најмањег елемента у делу низа од позиције ind до краја, па да се онда елемент на позицији ind замени са пронађеним минимумом. Алгоритам разложен на алгоритамске кораке изгледао би овако:

  • Нека је дат несортиран низ од n бројева и целобројна променљива ind.
  • У ind се памти индекс првог елемента. Пореде се сви следећи елементи у низу са елементом са индексом ind. Ако је неки од њих мањи, његов индекс памти се у ind.
  • Ако је ind различит од индекса првог елемента, мењају се места првог елемента и елемента са индексом ind.
  • У ind се памти индекс другог елемента. Пореде се сви следећи елементи у низу са елементом са индексом ind. Ако је неки од њих мањи, његов индекс памти се у ind.
  • Ако је ind различит од индекса другог елемента, мењају се места другог елемента и елемента са индексом ind.
  • … и тако редом.
  • Овај поступак понавља се закључно са претпоследњим елементом, након чега ће дати низ бити сортиран.

На пример, нека су у низу arr[5] дате закључне оцене ученика у виду несортираног низа целих бројева: arr[5] = { 5, 2, 4, 3, 4 }. У ind памти се индекс првог елемента 0. Пореде се сви следећи елементи у низу са елементом са индексом 0. Ако је неки од њих мањи, његов индекс памти се у ind:

arr[5] = { 5, 2, 4, 3, 4 }    ind = 0    2 < 5 ? DA    ind = 1
                                         4 < 2 ? NE
                                         3 < 2 ? NE
                                         4 < 2 ? NE

Пошто је ind различито од 0 мењају се места елементима са индексом 0 и индексом 1, па сада низ изгледа овако arr[5] = { 2, 5, 4, 3, 4 }.

У ind памти се индекс другог елемента 1. Пореде се сви следећи елементи у низу са елементом са индексом ind. Ако је неки од њих мањи, његов индекс памти се у ind:

arr[5] = { 2, 5, 4, 3, 4 }    ind = 1    4 < 5 ? DA    ind = 2
                                         3 < 4 ? DA    ind = 3
                                         4 < 3 ? NE

Пошто је ind различито од 1 мењају се места елементима са индексом 1 и индексом 3, па сада низ изгледа овако arr[5] = { 2, 3, 4, 5, 4 }.

У ind памти се индекс трећег елемента 2. Пореде се сви следећи елементи у низу са елементом са индексом ind. Ако је неки од њих мањи, његов индекс памти се у ind:

arr[5] = { 2, 3, 4, 5, 4 }    ind = 2    5 < 4 ? NE
                                         4 < 4 ? NE

Пошто ind није различито од 2 низ остаје не промењен.

У ind памти се индекс предпоследњег елемента 3. Пореди се последњи елемент у низу са елементом са индексом ind. Ако је последњи мањи, његов индекс памтим се у ind:

arr[5] = { 2, 3, 4, 5, 4 }    ind = 3    4 < 5 ? DA    ind = 4

Пошто је ind различито од 3 мењају се места елементима са индексом 3 и индексом 4, па сада низ изгледа овако arr[5] = { 2, 3, 4, 4, 5 }.

Овим су закључне оцене ученика сортиране од најмање ка највећој, односно, низ је сортиран у неопадајућем редоследу.

Имплементација алгоритма за сортирање избором

Напиши програм у програмском језику C којим ћеш демонстрирати поступак за сортирање низа на основу датог примера изнад.

Напиши програм у програмском језику C којим ћеш демонстрирати поступак за сортирање низа на основу датог примера изнад.

#include <stdio.h>

int main(void)
{
    int arr[] = { 5, 2, 4, 3, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    for (int i = 0; i < n - 1; i++)
    {
        int ind = i;
        for (int j = i + 1; j < n; j++)
            if (arr[j] < arr[ind])
                ind = j;
        if (ind != i)
        {
            int temp = arr[i];
            arr[i] = arr[ind];
            arr[ind] = temp;
        }
    }
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

Поједностављена верзија сортирања избором

Претходни алгоритам можеш „упростити” избацивањем променљиве ind што ће за последицу имати већи број замена.

Овај поступак понавља се закључно са претпоследњим елементом, након чега ће низ бити сортиран.

  • Нека је дат несортиран низ бројева.
  • Вредност првог елемента низа пореди се са сваким следећим. Ако је неки од њих мањи, мењају им се места.
  • Вредност другог елемента низа пореди се са сваким следећим. Ако је неки од њих мањи, мењају им се места.
  • … и тако редом.
#include <stdio.h>

int main(void)
{
    int arr[] = { 5, 2, 4, 3, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++)
            if (arr[j] < arr[i])
            {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

Овај упрошћени алгоритам је знатно једноставнији за разумевање, али се једноставност плаћа већим бројем замена – у овом случају, уместо три извршено је пет замена.

Претходни пример упрошћеног алгоритма са for петљама лако можеш превести у пример са while петљама:

#include <stdio.h>

int main(void)
{
    int arr[] = { 5, 2, 4, 3, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int i = 0, j = 0;
    while (i < n)
    {
        int j = i + 1;
        while (j < n)
        {
            if (arr[j] < arr[i])
            {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
            j++;
        }
        i++;
    }
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}