Selection Methods - Practices

The main strategy for the selection methods is to find, in each step, smaller or greater elements in unsorted arrays. Then place these elements as the first elements of sorted arrays. This strategy assumes that our array will have two parts: sorted and unsorted.

First method from this group is selection-sort:


SELECTION-SORT:
for i=1 to n-1 do
 min=a[i]
 pos=i
 for j=i+1 to n do 
  if(a[j]<min) then
   min=a[j]
   pos=j
  end_if
 end_for
 a[pos]=a[i]
 a[i]=min
end_for



Here we have, just like in the insertion-sort method, sorted and unsorted parts of our array. In the beginning the whole array is unsorted so we find the smallest value in our array and exchange it for the first element in the array.

After i-1 iterations we have the sorted part (a[1], ... , a[i-1]) and the unsorted part (a[i], ... , a[n]). In the next iteration we find the smallest value in the unsorted part and change its place with the first element from the sorted part, in that way this element becomes a part of the sorted part.

A critical part of this algorithm is that in each step it needs to find the smallest value from the unsorted part of our array.  This can be accomplished by splitting the unsorted part in groups and finding the smallest value in each group, termed the "local minimum". Now finding the smallest value of the whole unsorted part is finding the smallest value of all local minimums. In the next step we just need to find one local minimum.