Simple Selection Sort

 

Wolmer’s Trust High School for Girls

CAPE COMPUTER SCIENCE

 

Grade:  11                                          Teacher:  Mrs. McCallum-Rodney

 

 

Selection sort is the most conceptually simple of all the sorting algorithms. It works by selecting the smallest (or largest, if you want to sort from big to small) element of the array and placing it at the head of the array. Then the process is repeated for the remainder of the array; the next largest element is selected and put into the next slot, and so on down the line.

Because a selection sort looks at progressively smaller parts of the array each time (as it knows to ignore the front of the array because it is already in order), a selection sort is slightly faster than bubble sort.

The algorithm works as follows:

1. Find the minimum value in the list

2. Swap it with the value in the first position

3. Repeat the steps above for the remainder of the list (starting at the second position and advancing each time)

Effectively, we divide the list into two parts:

·         the sublist of items already sorted, which we build up from left to right and is found at the beginning,

·         and the sublist of items remaining to be sorted, occupying the remainder of the array.

 

 

1.      A repetition structure – FOR LOOP – is needed to control the number of phases needed. The number of phases is equal to the size of the array minus 1.

FOR phase =1 TO size_of_array - 1

2.      Within the for loop mentioned in (1) above, the following steps are needed:

a.       The minimum element number should be stored in a variable.  The minimum element number is equal to phase minus 1.

min = phase - 1

b.      Another repetition control structure is needed – FOR LOOP, that will control the index/positions to be compared with.  The first position to be compared with will be phase, and the last position to be compared with is the size of the array minus 1.

FOR index = phase TO size_of_array -1

c.       Within the for loop mentioned in 2(b) above, the following steps are needed:

                                                  i.      A selection structure is needed to determine if the value stored in position min is greater than value stored in element position index.

IF arr[min] > arr[index]

                                                ii.      If the answer to 2c(i) is true, then a new element will be stored in min.  This element position is index.

min = index

d.      When the for loop in 2(c) is exited, a selection structure is used to determine if the value was changed in min.

IF min <> phase -1

e.       Within the selection structure mentioned in 2(d), a swap will take place.  The following steps explains how the swap will take place:

                                                  i.      Create a temporary variable to store the value that is in position phase -1.

temp = arr[phase – 1]

                                                ii.      Store the value that is in position min into position phase -1.

arr[phase-1] = arr[min]

                                              iii.      Store the value in temp into position min.

arr[min] = temp

3.      No further instructions are need when the for loop in 1 above is exited.

 

SIMPLE SELECTION SORT FLOWCHART

___________________________________________________________________