Сортирање селекцијом — разлика између измена
Садржај обрисан Садржај додат
Нема описа измене |
Нема описа измене |
||
Ред 8:
}}
'''Сортирање селекцијом ''' ({{јез-енг|selection sort}}) је [[алгоритам]] [[сортирање|сортирања]] који се заснива на принципу [[груба сила|грубе силе]]. Овај алгоритам још познат и под именом метод селекције. Када кажемо груба сила мислимо обрађивање сваког елемента посебно. Овај алгоритам је нарочито употребљив код controlflow архитектуре (у њој пишемо програме који контролишу ток података кроз хардвер). Сортирање селекцијом сортира низ елемената тако што га прво целог претражи, како би нашао први подобан елемент (нпр. највећи или најмањи) и сместио га на прво место у низу. Тада претражује цели остатак низа (без првог места) како би нашао други такав елемент и сместио на друго место у низу. Онда се поступак понавља за остатак низа без првог и другог места итд. Ово му доноси временску сложеност -{O(n²)}-. Количина коришћене [[рачунарска меморија|меморије]] је -{O(1)}- уколико се измене врше на оригиналном низу, а -{O(n)}- ако се прави сортирана копија низа.
Сортирање селекцијом може бити [[стабилност (сортирање)|стабилно]], али и не мора, зависно од имплементације.
Ред 78:
}
</source>
== Имплементација у програмском језику -{Python}- ==
<source lang="c">
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]),
</source>
== Имплементација у програмском језику -{Java}- ==
<source lang="c">
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;
}
}
</source>
== Сложеност ==
У поређењу са другим алгоритмима, код сортирања селекцијом није тешко установити колика је сложеност. Наиме, имамо n елемената и исто тако n-1 поређења након чега их доводимо на прво место. Проналажење следећег најмањег елемента захтева претраживање n-1 итд. Тиме добијамо формулу
<math>(n-1)+(n-2)+...+1 =
\sum_{i=1}^{n-1}i=
\sum_{i=1}^{n-1}\binom{i}{1}</math>
следеће што треба да урадимо је да се сетимо формуле из комбинаторике
<math>k\in\mathbb{N}, k \geqslant r</math>,
:<math>\sum^k_{i=r}{i\choose r}={k+1\choose r+1}</math> - ову формулу можемо доказати индукцијом.
Када применимо ову формулу добијамо
<math>\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)</math>
добијамо временску сложеност <math>O(n^2)</math> а пошто имамо n елемената на улазу просторна сложеност је <math>O(n)</math>
== Референце ==
{{reflist}}
{{refbegin}}
* [[Donald Knuth]]. ''[[The Art of Computer Programming]]'', Volume 3: ''Sorting and Searching'', Third Edition. Addison–Wesley, 1997. {{ISBN|0-201-89685-0}}. Pages 138–141 of Section 5.2.3: Sorting by Selection.
* Anany Levitin. ''Introduction to the Design & Analysis of Algorithms'', 2nd Edition. {{ISBN|0-321-35828-7}}. Section 3.1: Selection Sort, pp 98–100.
* [[Robert Sedgewick (computer scientist)|Robert Sedgewick]]. ''Algorithms in C++, Parts 1–4: Fundamentals, Data Structure, Sorting, Searching: Fundamentals, Data Structures, Sorting, Searching Pts. 1–4'', Second Edition. Addison–Wesley Longman, 1998. {{ISBN|0-201-35088-2}}. Pages 273–274
{{refend}}
[[Категорија:Алгоритми сортирања]]
| |||