Introduction



Selection sort is one of the simplest sorting techniques.Sorting Techniques are mostly used in Highscore calculation program.I have made it more efficient by adding a line in standard selection sort code

Background



Selection sort is sorting technique with a simple logic.
Consider the following example:
Problem:We have a array on 10 numbers we have to arrange them in ascending order using selection sort.Array is 4,3,6,5,8,1,9,0,2,7
Solution:
Iteration 1:We select the first element 4 and swap it with the smallest element in array '0'.
Array after iteration 1:0,3,6,5,8,1,9,4,2,7
Iteration 2:Discard first element as it is sorted now select second element swap it with the first element i.e swap 3 with 1.This process continues until array is sorted.
Array after iteration 2:0,1,6,5,8,3,9,4,2,7
Array after iteration 3:0,1,2,5,8,3,9,4,6,7
Array after iteration 4:0,1,2,3,8,5,9,4,6,7
Array after iteration 5:0,1,2,3,4,5,9,8,6,7
Array after iteration 6:0,1,2,3,4,5,9,8,6,7[If the element consideres is smallest it reamins there here 5 remains at same place]
Array after iteration 7:0,1,2,3,4,5,6,8,9,7
Array after iteration 8:0,1,2,3,4,5,6,7,9,8
Array after iteration 9:0,1,2,3,4,5,6,7,8,9
Note that for selection sort there are n-1 iteration where n is the number of elements
The Line I added in the code from standard code makes it more efficient for longer arrays

The code


In This example I have used templates It sorts variables of different data types

Code:
//selection sort
#include<iostream.h>
#include<conio.h>
template<class T>
void selectsort(T a[],int size)
{
    T temp,small;
    int pos,i,j,k;
    for(i=0;i<size;i++)
    {
      pos=i;\\I have found his all important line mssing in many standard books 
      small=a[i];
      for(j=i+1;j<size;j++)
      {
 if(a[j]<small)
 {
     small=a[j];
     pos=j;
 }
      }
      temp=a[i];
      a[i]=a[pos];
      a[pos]=temp;
      cout<<"The array after iteration- "<<i+1<<" is ";
      for(k=0;k<size;k++)
    cout<<a[k]<<" ";
      cout<<"\n";
    }
}
void main()
{
   clrscr();
   cout<<"\t SELECTION SORT PROGRAM\n";
   int a[50],size,choice,i;
   char b[50];
   float c[50];
   start:
   cout<<"Enter size of array\n";
   cin>>size;
   cout<<"Enter type of array\n1.Character\n2.Integer\n3.Float\n";
   cin>>choice;
   switch(choice)
   {
     case 1:
    cout<<"Enter elements of character array\n";
    for(i=0;i<size;i++)
       cin>>b[i];
    selectsort(b,size);
    cout<<"Enter the character array is\n";
    for(i=0;i<size;i++)
      cout<<b[i]<<" ";
    break;
     case 2:
    cout<<"Enter elements of integer array\n";
    for(i=0;i<size;i++)
       cin>>a[i];
    selectsort(a,size);
    cout<<"Enter the integer array is\n";
    for(i=0;i<size;i++)
      cout<<a[i]<<" ";
    break;
     case 3:
    cout<<"Enter elements of float array\n";
    for(i=0;i<size;i++)
       cin>>c[i];
    selectsort(b,size);
    cout<<"Enter the character array is\n";
    for(i=0;i<size;i++)
      cout<<b[i]<<" ";
    break;
     default:
   cout<<"Invalid choice\n";
   goto start;
   }
}

Last edited by rockyrakster; 26Aug2009 at 19:37..