Selection sort is a simple sorting algorithm with asymptotic complexity . In comparison with other quadratic sorting algorithms it almost always outperforms bubble sort, but it is usually slower than insertion sort. The advantage of selection sort over algorithms with
(quicksort, heapsort, merge sort) asymptotic complexity is it's constant memory complexity.
Description
The idea of selection sort is, that if we sort the array from largest to smallest element, than the first element of the sorted array will be the one with the largest value. Second will be the largest element of the rest of the array. Third will be the largest element of the new rest of the array (initial array without the two already sorted elements)...
So we can iteratively select the largest element of the (reduced) array, swap it with the first element and than reduce the problem size by 1 (sort only the rest of the array). When there remains only one element to sort, the algorithm terminates.
Visualization
Example
(3 2 8 7 6) // 8 is the largest value, swap it with 3 at index 0
(8 2 3 7 6) // 7 is the largest value, swap it with 2 at index 1
(8 7 3 2 6) // 6 is the largest value, swap it with 3 at index 2
(8 7 6 2 3) // 3 is the largest value, swap it with 2 at index 3
(8 7 6 3 2) // sorted
Code
1.
function selectionSort(array a)
2.
for
i in
0
-> a.length -
2
do
3.
maxIndex = i
4.
for
j in (i +
1
) -> (a.length -
1
)
do
5.
if
a[j] > a[maxIndex]
6.
maxIndex = j
7.
swap(a[i], a[maxIndex])
01.
/**
02.
* Selection sort (descending order)
03.
* @param array array to be sorted
04.
*/
05.
public
static
void
selectionSort(
int
[] array) {
06.
for
(
int
i =
0
; i < array.length -
1
; i++) {
07.
int
maxIndex = i;
08.
for
(
int
j = i +
1
; j < array.length; j++) {
09.
if
(array[j] > array[maxIndex]) maxIndex = j;
10.
}
11.
int
tmp = array[i];
12.
array[i] = array[maxIndex];
13.
array[maxIndex] = tmp;
14.
}
15.
}
01.
/**
02.
* Selection sort (descending order)
03.
* @param array array to be sorted
04.
* @param size size of the array
05.
*/
06.
void
selectionSort(
int
array[],
int
size) {
07.
for
(
int
i = 0; i < size - 1; i++) {
08.
int
maxIndex = i;
09.
for
(
int
j = i + 1; j < size; j++) {
10.
if
(array[j] > array[maxIndex]) maxIndex = j;
11.
}
12.
int
tmp = array[i];
13.
array[i] = array[maxIndex];
14.
array[maxIndex] = tmp;
15.
}
16.
}
01.
/**
02.
* Selection sort (descending order)
03.
* @param array array to be sorted
04.
*/
05.
public
static
void
SelectionSort(
int
[] array)
06.
{
07.
for
(
int
i = 0; i < array.Length - 1; i++)
08.
{
09.
int
maxIndex = i;
10.
for
(
int
j = i + 1; j < array.Length; j++)
11.
{
12.
if
(array[j] > array[maxIndex]) maxIndex = j;
13.
}
14.
int
tmp = array[i];
15.
array[i] = array[maxIndex];
16.
array[maxIndex] = tmp;
17.
}
18.
}
01.
procedure
SelectSort(
var
X : ArrayType; N :
integer
);
02.
var
03.
I,
04.
J,
05.
K,
06.
Y :
integer
;
07.
begin
08.
for
I :=
1
to
N -
1
do
09.
begin
10.
K := I;
11.
Y := X[I];
12.
for
J := (I +
1
)
to
N
do
13.
if
(X[J] < Y)
then
14.
begin
15.
K := J;
16.
Y := X[J]
17.
end
;
18.
X[K] := X[J];
19.
X[I] := Y;
20.
end
21.
end
;