Home Practices Page 5 - Sort This Sort That

# Selection Methods - Practices

One of the main activities in algorithms and programs, whose purpose is manipulating data, is sorting. So if you write these kinds of programs-what kind of method for sorting data is best? In this article I will present some algorithms for sorting and their advantages and weaknesses.

Rating:  / 21
February 25, 2004

SEARCH DEV SHED

TOOLS YOU CAN USE

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]=minend_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.

 >>> More Practices Articles          >>> More By Djordje Popovic