Suppose A is an array of N Integer values. We want to sort A in ascending order, that is, so A(1) is smallest and A(N) is largest.
Selection Sort is an algorithm to do this as follows: We have the top part of the array, which is done, and the bottom part of the array, which is not yet done. We repeatedly find the smallest element in the unsorted part of the array and swap it with the first element in the unsorted part of the array.
That is:
Do I = 1, N
Call FINDSMALL(A, I, N, SMALLSUB)
Call SWAP(A(I), A(SMALLSUB))
End Do
Here FINDSMALL is a subroutine which finds SMALLSUB = the subscript of the smallest value of A(J) for J between I and N; and SWAP is a subroutine which switches the values of A(I) and A(SMALLSUB).
FINDSMALL could easily be a Integer-valued function instead.
We could use an IF statement in the main program or in SWAP to avoid swapping values if I = SMALLSUB.
To sort in descending order instead (A(1) largest and A(N) smallest), we would use a very similar subroutine called FINDLARGE instead.
An alternate way to sort in ascending order is to find the largest value and swap with the last element in the unsorted part of the array.
Of course, instead of using subroutines, we could easily write all the code we need in the main program, but it is probably better design to use the subroutines.
Example
Suppose the initial values in A are:
67 33 21 4 84 49 15 55 75 6
\----------------------------------------------/
unsorted part of the array
I = 1: FINDSMALL(A, 1, 10, SMALLSUB)
(We find SMALLSUB = 4.)
SWAP(A(1), A(4))
4 33 21 67 84 49 15 55 75 6
\-/ \-----------------------------------------/
sorted unsorted part of the array
I = 2: FINDSMALL(A, 2, 10, SMALLSUB)
(We find SMALLSUB = 10.)
SWAP(A(2), A(10))
4 6 21 67 84 49 15 55 75 33
\-----/ \------------------------------------/
sorted unsorted part of the array
I = 3: FINDSMALL(A, 3, 10, SMALLSUB)
(We find SMALLSUB = 7.)
SWAP(A(3), A(7))
4 6 15 67 84 49 21 55 75 33
\----------/ \-------------------------------/
sorted part unsorted part of the array
I = 4: FINDSMALL(A, 4, 10, SMALLSUB)
(We find SMALLSUB = 7.)
SWAP(A(4), A(7))
4 6 15 21 84 49 67 55 75 33
\---------------/ \--------------------------/
sorted part unsorted part of the array
I = 5: FINDSMALL(A, 5, 10, SMALLSUB)
(We find SMALLSUB = 10.)
SWAP(A(5), A(10))
4 6 15 21 33 49 67 55 75 84
\--------------------/ \---------------------/
sorted part unsorted part
I = 6: FINDSMALL(A, 6, 10, SMALLSUB)
(We find SMALLSUB = 6.)
SWAP(A(6), A(10))
4 6 15 21 33 49 67 55 75 84
\-------------------------/ \----------------/
sorted part of the array unsorted part
I = 7: FINDSMALL(A, 7, 10, SMALLSUB)
(We find SMALLSUB = 8.)
SWAP(A(7), A(8))
4 6 15 21 33 49 55 67 75 84
\------------------------------/ \-----------/
sorted part of the array unsorted part
I = 8: FINDSMALL(A, 8, 10, SMALLSUB)
(We find SMALLSUB = 8.)
SWAP(A(8), A(8))
4 6 15 21 33 49 55 67 75 84
\-----------------------------------/ \-----/
sorted part of the array unsorted
I = 9: FINDSMALL(A, 9, 10, SMALLSUB)
(We find SMALLSUB = 9.)
SWAP(A(9), A(9))
4 6 15 21 33 49 55 67 75 84
\-----------------------------------------/ \--/
sorted part of the array unsorted
At this point we are actually done, as the last number must be the largest.
In the process, we have done 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45 comparisons and 9 swaps. For an array of 10 elements, Selection Sort will always do 45 comparisons and 9 swaps.