# How does selection sort sort?

I've found the following algorithm for selection sort on the internet.

program SelectionSort(input,output);
var
A : Array[1..80] of Integer;
n, i, j, k, m, loc, temp : Integer;
begin
writeln('size of the array?');

for i := 1 to n do

for k := 1 to n - 1 do
begin
m := A[k];
loc := k;
for j := k + 1 to n do
begin
if m > A[j] then
begin
m := A[j];
loc := A[j];
loc := j;
end;
end;
temp := A[k];
A[k] := A[loc];
A[loc] := temp;
end;

for i := 1 to n do
begin
writeln(A[i] : 3);
end;

end.


I'd like to gain a better understanding of how it actually does the sorting. Could someone please help me with this?

• Are you interested in the algorithm or this specific implementation of it in this specific language? To study the algorithm, it's usually better to look at pseudocode. Actual code is usually harder to understand since the fundamental steps can be obscured by the idiosyncracies of the programming language or programmer and by routines for input/output. – David Richerby Mar 3 '15 at 21:10
• Start by reading Selection Sort on Wikipedia. Should help to get an idea what the algorithm tries to perform. It even has a nice animation! – Hendrik Jan Mar 3 '15 at 23:38

Neither the code you have nor the Wikipedia article highlight the concept of selection sort. Therefore, consider this (functional) pseudocode:

def selection-sort []         = []
|   selection-sort x::xs as l =
let m = min l
in
m::(selection-sort (delete m l))
end;


Here the idea is more clear

$\ \$1. Select the minimum from the list and delete it.
$\ \$2. Sort the remainder recursively.
$\ \$3. Prepend the minimum.

The same works the other way around with the maximum, obviously.

Iterative code on arrays works slightly differently -- but the idea remains the same.

• It's helpful to note the duality with insertion sort. – Raphael Mar 4 '15 at 7:03
• A common exercise is to improve above pseudocode so that min and delete are one operation, approximately halving runtime. – Raphael Mar 4 '15 at 7:04