Sorting by Selection

Here explain sorting of random ordered n integers in to ascending order using Selection. Firstly look at unsorted and sorted arrays  It is simple and basic algorithm with simple two steps.

Comparing sorted and Unsorted arrays we can see that it can be done using following steps

1. Find the smallest element in unsorted array .
2.  Place it (smallest element ) in position a[0] .

This process is shown in figure below.

//This code is for sort  first element//

 Min = a[0];

      for(j=1;j<=n;j++){

 if(a[j]<min){

 min = a[j];}}

 a[0]= min;

 From the figure we can see that 3 is to be selected as smallest element and placed into a[0] .But the problem is 20 is missing that was in previous a[0] position.To avoid this problem we will save the element 20 before 3 placing into a[0]. It can done with temporary variable. After placing 3 into a[0], 20 from temporary variable need placed into a[6] which is previous position of 3. Now we successfully sort the first element. Figure illustrate the sorted and unsorted parts. We don't want consider sorted part then. In unsorted part we need to do same process again and again. how can we write general code?.ok..Before general code just look the figure that an array is sorted by selection in step by step. We can easily grasp the algorithm. Also from figure we can see that the array taking 7 steps to sort 8 element array.So in general case we need (n-1) iteration to sort n element array.   

      

 Algorithm Description:    While there are still elements in the unsorted part of the array do      

       1.      Find the minimum and place it as first element in unsorted part of array a[n].      

       2.      Exchange the min in the unsorted of the array with the first element a[i] in the unsorted array.    

  

Implementation in C:  

for(i=0;i<=n-2;i++){

  min=a[i];

    for(j=i+1;j<=n;j++){

     if(a[j]<min){ 

    min=a[j];

     }

    a[i]=min;                  }}    

Posted in: