Сортирање избором¶
Постоји више алгоритама које можеш да примениш како би сортирао елементе низа бројева, а један од најједноставнијих је алгоритам за сортирање избором (енгл. Selection Sort).
Опис алгоритма¶
Идеја је да је да се сортирани низ формира тако што се за сваки индекс 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 којим ћеш демонстрирати поступак за сортирање низа на основу датог примера изнад.
#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;
}
Имплементација са for петљама¶
Претходни алгоритам можеш „упростити” избацивањем променљиве 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;
}
Овај упрошћени алгоритам је знатно једноставнији за разумевање, али се једноставност плаћа већим бројем замена - у овом случају, уместо три извршено је пет замена.
Имплементација са while петљама¶
Претходни пример упрошћеног алгоритма са 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;
}
Мане сортирања избором и мане статички алоцираних низова¶
Користећи сортирање избором реши задатак Сортирање бројева у програмском језику C. Могуће решење задатка алгоритмом за сортирање избором демонстрира мане тог алгоритма и статички алоцираних низова:
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, arr[100000];
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
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\n", arr[i]);
return 0;
}
Због ограничења датог текстом задатка о димензији низа \(n(1\le{n}\le{10^{5}})\),
статичком алокацијом низа од \(100000\) елемената типа int, резервише се
велика количина меморије. На то ће ти указати и сâмо развојно окружење поруком:
C6262: Function uses 400020 bytes of stack. Consider moving some data to heap..
Непоштовање ограничења задатих текстом задатка засигурно ће резултирати грешком
приликом извршавања задатка са тест примерима на Петљи, тако да смањење
димензије низа не може да буде решење.
Како је текстом задатка задато и ограничење о максималној вредности сваког
елемента низа које треба бити мање од \(200000\), задатак није могуће решити
променом типа елемената низа са int на short int, па ни на тај начин се не
може „уштедети” на заузећу меморије.
Поред упозорења о великом заузећу меморије, задатак ће се извршити без проблема
на твом рачунару, међутим, како је текстом задатка задато и предвиђено време
извршавања програма које не сме да пређе две секунде, извршавањем програма над
деветим и десетим тест примером на Петљи систем ће избацити грешку TLE о
временском прекорачењу, јер се овим тест примерима сортира велики број
елемената низа (преко \(80000\) елемената).
Из свега наведеног можеш да закључиш да је оправдано постојање различитих начина за алокацију низа и различитих алгоритама за сортирање низа. У овом задатку сортирање великог статички алоцираног низа није добро решење. Задатак са оваквим ограничењима могуће је решити у програмском језику C динамичком алокацијом низа и применом других алгоритама сортирања, што ћеш учити у следећем разреду.