|
}}
In [[computer science]], '''selection sort''' is an [[in-place algorithm|in-place]] [[comparison sort|comparison]] [[sorting algorithm]]. It has ana [[Big O notation|O]](''n''<sup>2</sup>) [[time complexity]], which makes it inefficient on large lists, and generally performs worse than the similar [[insertion sort]]. Selection sort is noted for its simplicity and has performance advantages over more complicated algorithms in certain situations, particularly where [[auxiliary memory]] is limited.
The algorithm divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.
The time efficiency of selection sort is quadratic, so there are a number of sorting techniques which have better time complexity than selection sort. One thing which distinguishes selection sort from other sorting algorithms is that it makes the minimum possible number of swaps, {{nobr|''n'' − 1}} in the worst case.
== Example ==
|-
| ()
| {{ts|ar}}style="text-align:right;" | (1112, 25, 1264, 2211, 6422)
| 11
|-
| (11)
| {{ts|ar}}style="text-align:right;" | (25, 1264, 2212, 6422)
| 12
|-
| (11, 12)
| {{ts|ar}}style="text-align:right;" | (2564, 2225, 6422)
| 22
|-
| (11, 12, 22)
| {{ts|ar}}style="text-align:right;" | (25, 64)
| 25
|-
| (11, 12, 22, 25)
| {{ts|ar}}style="text-align:right;" | (64)
| 64
|-
| (11, 12, 22, 25, 64)
| style="text-align:right;" | ()
| {{ts|ar}} |()
|
|}
== Implementations ==
{{unreferenced section|date=May 2019}}
Below is an implementation in [[C (programming language)|C]].
<syntaxhighlight lang="c" style="overflow:auto; width:auto;" line="1">
if (jMin != i)
{
swap(&a[i], &a[jMin]);
}
}
== Complexity ==
Selection sort is not difficult to analyze compared to other sorting algorithms, since none of the loops depend on the data in the array. Selecting the minimum requires scanning <math>n</math> elements (taking <math>n-1</math> comparisons) and then swapping it into the first position. Finding the next lowest element requires scanning the remaining <math>n-1</math> elements (taking <math>n-2</math> comparisons) and so on. Therefore, the total number of comparisons is
: <math>(n-1)+(n-2)+...\dots+1 =
\sum_{i=1}^{n-1}i</math>
By [[arithmetic progression]],
: <math>\sum_{i=1}^{n-1}i=
\frac{(n-1)+1}{2}(n-1)=
\frac{1}{2}n(n-1)=
\frac{1}{2}(n^2-n)</math>
which is of complexity <math>O(n^2)</math> in terms of number of comparisons. Each of these scans requires one swap for <math>n-1</math> elements (the final element is already in place).
== Comparison to other sorting algorithms ==
== Variants ==
[[Heapsort]] has been described as "nothing but an implementation of selection sort using the right [[data structure]]."<ref>{{cite book |first=Steven |last=Skiena |author-link=Steven Skiena |title=The Algorithm Design Manual |edition=3rd |publisher=Springer |year=2008 |page=116 |chapter=Searching and Sorting |isbn=978-3-030-54255-9 |quote=The name typically given to this algorithm, ''heapsort'', obscures the fact that the algorithm is nothing but an implementation of selection sort using the right data structure. |doi=10.1007/978-3-030-54256-6_4}}<!--DOI for chapter--></ref> It greatly improves the basic algorithm by using an [[implicit data structure|implicit]] [[heap (data structure)|heap]] [[data structure]] to speed up findingfind and removingremove the lowest datum. If implemented correctly, the heap will allow finding the nexteach lowest element in <math>\Theta(\log n)</math> time, instead of normal selection sort's <math>\Theta(n)</math> for the inner loop in normal selection sort, reducing the total running time to <math>\Theta(n\log n)</math>.
A bidirectional variant of selection sort (called '''double selection sort''' or sometimes '''cocktail sort''' due to its similarity to [[cocktail shaker sort]]) finds ''both'' the minimum and maximum values in the list in every pass. This requires three comparisons per two items (a pair of elements is compared, then the greater is compared to the maximum and the lesser is compared to the minimum) rather than regular selection sort's one comparison per item, but requires only half as many passes, a net 25% savings.
last := length(A) - 1;
{ The first iteration is written to look very similar to
the subsequent ones, but without swaps. }
but without swaps. }
nextMax := A[last];
for i := last - 1 downto 0 do
while last > 0 do begin
{ Each main loop searches for the new nextMax while
swapping items equal to prevMax into place. }
prevMax := nextMax;
nextMax := A[last];
-->
===== Pyramid-Select-Sort variant =====
You create pyramit of minimals.
{|
|-
| time: as select sort (11 ms, when tim-sort have 1 ms)
|-
| memory: array-from + array-to + array of index (length=n)
|-
| compares for n=1000: 8000-9000 (when tim-sort have 8500)
|}
<syntaxhighlight>
SCHEMA
7 14 0 4 6 13 5 8 10 3 2 1 15 12 11 9
---- --- ---- --- ---- --- ----- ---- line = compare (a,b)
7 0 6 5 3 1 12 9 pyramid level 1 (in code use index, for schema use values)
------ ------ ----- ------- can save as array [ [7,0,6,5,3,1,12,9], [0,5,1,9] [0,1] ]
0 5 1 9
---------- ------------
0 1
--------------------- First pyramid take 15 compares.
0 - save, rebuild branch with new value
7 4 6 5 3 1 12 9
------
4 5
----------
4 1
--------------------- Next pyramid take 3 compares.
1 - save
7 4 6 5 3 2 12 9
---
2 9
--------------
4 2
------------------- Next pyramid take 3 compares.
2 - save
7 4 6 5 3 -1 12 9
3 9 (when -1 copy second value)
-----------------
4 3
---------------- Next pyramid take 2 compares.
3 - save
===================================================================
(15+3+3+2) + (+2+2+2+3+2+2+1+1+1+1+1+1+1) =
= 23+20 = 43 compares (tim-sort 47, sorted-list-merging 44)
</syntaxhighlight>
Code:
<syntaxhighlight lang="javascript">
<div></div>
<script>
// build first pyramid tree of minimal values
function pyramid_part1_buildPyramid(list, cmp, i_start, i_end, size) //bounds[i],bounds[i+1],bounds[i+2] | sortListMerge_3aBounds
{
var cycles = 0;
var moves = 0;
var i,j,k, k_end, lvl, lvlp1;
var pyramid = [];
i = i_start;
j = i_start+1; // i_end = j_start
k = 0;
lvl = 0;
pyramid[lvl] = [];
while (j<i_end)// && mm.func.algStopByTimeCheck())
{
if (cmp(list[i], list[j])>0)
{swap(list, i, j);}
pyramid[lvl][k] = i; i+=2; j+=2; k++;
cycles++;
}
if (i<i_end) { // pokud je size liche cislo, pak pridej posledni prvek a preswapuj to (toho vyuziji pozdeji v part2)
if (cmp(list[i-2], list[i])>0)
{
tmp = list[i];
list[i ] = list[i-1];
list[i-1] = list[i-2];
list[i-2] = tmp;
moves += 4;
pyramid[lvl][k] = i;
}
else {if (cmp(list[i-1], list[i])>0)
{
tmp = list[i];
list[i ] = list[i-1];
list[i-1] = tmp;
moves += 3;
}}
}
i_end = k;
lvlp1 = lvl + 1;
while (i_end>1)// && mm.func.algStopByTimeCheck())
{
pyramid[lvlp1] = [];
k = 0;
i = 0;
j = 1; // i+1
while (j<i_end)// && mm.func.algStopByTimeCheck())
{
cycles++;
if (cmp(list[ pyramid[lvl][i] ], list[ pyramid[lvl][j] ])>0)
{pyramid[lvlp1][k] = pyramid[lvl][j]; i+=2; j+=2; k++; cycles++; continue;}
else {pyramid[lvlp1][k] = pyramid[lvl][i]; i+=2; j+=2; k++; cycles++; continue;}
}
if (i<i_end) {pyramid[lvlp1][k] = pyramid[lvl][i]; k++;}
lvl++;
lvlp1++;
i_end = k;
cycles++;
}
glob.cycles += cycles;
glob.moves += moves;
return [pyramid, lvl, pyramid[lvl][0], (size>>1)<<1 != size]; // vrat pyramidu, last item (staci asi last level), last operacia left-right (ta se da zjistit z predchozi vetve, kde se v ni nachazi)
}
function pyramid_part2_rebuildPyramid(pyramid, last_lvl, bool, list, cmp, i_end)
{
var cycles = 0;
var moves = 0;
var lvl, lvl_end, pos, val, val2, i, j, a, b, empty=-1;
val = pyramid[last_lvl][0];
pos = val>>1; // pozice zleva
lvl_endm1 = last_lvl
if (bool==true && ((val & 0x01) == 0) && ((pos<<1)==i_end-3) ) // kdyz je size liche cislo a dojde k eliminaci n-2, n-1 (n), tak posun posledni 2 cisla
{ // a zkontroluj strom pro nove hodnoty
bool = false;
list[val] = list[val+1]; // pokud pouzivate indexy, tak tady je treba to resit jinak, jinak ztratite hodnotu (n-2)
list[val+1] = list[val+2];
moves++;
val2 = val; // a zmena je tady (proti verzi bez bool==true)
pyramid[0][pos] = val2;
for (lvl=0; lvl<lvl_endm1 && mm.func.algStopByTimeCheck(); lvl++)
{
cycles++;
if ((pos & 0x01) == 0)
{
if (pos==pyramid[lvl].length-1)
{
pos = pos>>1;
pyramid[lvl+1][pos] = val2; //val2 = val2;
continue;
}
b = pyramid[lvl][pos+1];
a = pyramid[lvl][pos];
pos = pos>>1;
if (b==empty)
{pyramid[lvl+1][pos] = a; val2 = a; continue;}
if (cmp(list[a], list[b])>0)
{pyramid[lvl+1][pos] = b; val2 = b; continue;}
pyramid[lvl+1][pos] = a; val2 = a;
}
else {
a = pyramid[lvl][pos-1];
b = pyramid[lvl][pos];
pos = pos>>1;
if (a==empty)
{pyramid[lvl+1][pos] = b; val2 = b; continue;}
if (cmp(list[a], list[b])>0)
{pyramid[lvl+1][pos] = b; val2 = b; continue;}
pyramid[lvl+1][pos] = a; val2 = a;
}
}
pyramid[lvl_endm1] = [val2];
}
else {if ((val & 0x01) == 0) // je sude? vymen za liche a prepocitej vsechna nutna porovnani
{
val2 = val + 1;
pyramid[0][pos] = val2;
for (lvl=0; lvl<lvl_endm1; lvl++)// && mm.func.algStopByTimeCheck(); lvl++)
{
cycles++;
if ((pos & 0x01) == 0)
{
if (pos==pyramid[lvl].length-1)
{
pos = pos>>1;
pyramid[lvl+1][pos] = val2; //val2 = val2;
continue;
}
b = pyramid[lvl][pos+1];
a = pyramid[lvl][pos];
pos = pos>>1;
if (b==empty)
{pyramid[lvl+1][pos] = a; val2 = a; continue;}
if (cmp(list[a], list[b])>0)
{pyramid[lvl+1][pos] = b; val2 = b; continue;}
pyramid[lvl+1][pos] = a; val2 = a;
}
else {
a = pyramid[lvl][pos-1];
b = pyramid[lvl][pos];
pos = pos>>1;
if (a==empty)
{pyramid[lvl+1][pos] = b; val2 = b; continue;}
if (cmp(list[a], list[b])>0)
{pyramid[lvl+1][pos] = b; val2 = b; continue;}
pyramid[lvl+1][pos] = a; val2 = a;
}
}
pyramid[lvl_endm1] = [val2];
}
else { // //nebo je liche, odstran (ale, to jeste nevim, jakym zpusobem, melo by ho
val2 = empty;
pyramid[0][pos] = val2;
for (lvl=0; lvl<lvl_endm1; lvl++)// && mm.func.algStopByTimeCheck(); lvl++)
{
cycles++;
if ((pos & 0x01) == 0)
{
if (pos==pyramid[lvl].length-1)
{
pos = pos>>1;
pyramid[lvl+1][pos] = val2; //val2 = val2
continue;
}
a = pyramid[lvl][pos];
b = pyramid[lvl][pos+1];
pos = pos>>1;
if (a!==empty && b!==empty)
{
if (cmp(list[a], list[b])>0)
{pyramid[lvl+1][pos] = b; val2 = b; continue;}
else {pyramid[lvl+1][pos] = a; val2 = a; continue;}
}
if (b!==empty)
{pyramid[lvl+1][pos] = b; val2 = b; continue;}
pyramid[lvl+1][pos] = a;
val2 = a;
}
else {
a = pyramid[lvl][pos-1];
b = pyramid[lvl][pos];
pos = pos>>1;
if (a!==empty && b!==empty)
{
if (cmp(list[a], list[b])>0)
{pyramid[lvl+1][pos] = b; val2 = b; continue;}
else {pyramid[lvl+1][pos] = a; val2 = a; continue;}
}
if (a!==empty)
{pyramid[lvl+1][pos] = a; val2 = a; continue;}
pyramid[lvl+1][pos] = b;
val2 = b;
}
}
pyramid[lvl_endm1] = [val2];
}}
glob.moves += moves;
glob.cycles += cycles;
return [pyramid, lvl_endm1, pyramid[lvl_endm1][0], bool]; // vrat pyramidu, last item (staci asi last level), last operacia left-right (ta se da zjistit z predchozi vetve, kde se v ni nachazi)
}
function XsortSelectPyramid_m3_v1(cmp, start, end, n) // select minimal value, save, use before compares (memory: input-array, tree (n-1, only-index), out-array)
{
// var o = mm.func.sortResetUndefined(cmp, start, end, n);
if (o.size<2) {return o.n;}
var pyramid_data, i, x, y, zz, bool;
x = o.n;
y = o.n==1 ? 2 : 1;
pyramid_data = pyramid_part1_buildPyramid(arr[x], o.fn_cmp, o.start, o.end, o.size); // create pyramid of index from minimal values of pair
i = o.start;
arr[y][i] = arr[x][pyramid_data[2]];
o.moves++;
i++;
while (i<o.end)
{
pyramid_data = pyramid_part2_rebuildPyramid(pyramid_data[0], pyramid_data[1], pyramid_data[3], arr[x], o.fn_cmp, o.end)
arr[y][i] = arr[x][pyramid_data[2]];
o.moves++;
i++;
}
glob.moves += o.moves;
return y;
}
// code not optimalized - draft version from my tester
function sortCompare (a, b)
{
glob.cmps++;
var c = a - b;
return c>0 ? 1 : (c<0 ? -1 : 0);
};
function swap (list, a, b)
{
if (a==b) {return;}
var tmp = list[a];
list[a] = list[b];
list[b] = tmp;
glob.moves += 3;
};
var arr = [null, [7,7,4,3,4,7,6,7,0,1,0,6,7,2,2,4], [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1]]
var glob = {moves: 0, cycles: 0, cmps: 0};
var o = {start: 0, end: 16, size: 16 - 0, n: 1, moves: 0, cycles: 0, fn_cmp: sortCompare};
var log = [], i=0, n;
log[i++] = 'array-before ' + JSON.stringify(arr[1])
o.n = XsortSelectPyramid_m3_v1(o.fn_cmp, o.start, o.end, o.n);
log[i++] = 'array-after ' + JSON.stringify(arr[o.n])
log[i++] = 'glob ' + JSON.stringify(glob)
log[i++] = 'n ' + JSON.stringify(o.end - o.start)
document.getElementsByTagName('DIV')[0].innerHTML = log.join('<br>')
/*
array-before [7,7,4,3,4,7,6,7,0,1,0,6,7,2,2,4]
array-after [0,0,1,2,2,3,4,4,4,6,6,7,7,7,7,7]
glob {"moves":22,"cycles":70,"cmps":47}
n 16
*/
</script>
</syntaxhighlight>
== See also ==
{{sorting}}
[[Category:Sorting algorithms]]
[[Category:Comparison sorts]]
[[Category:Articles with example C code]]
| 