0
$\begingroup$

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?');
  read(n);

  for i := 1 to n do
   read(A[i]);

  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;

  readln();
  readln();
end.

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

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – David Richerby Mar 3 '15 at 21:10
  • $\begingroup$ 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! $\endgroup$ – Hendrik Jan Mar 3 '15 at 23:38
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.