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;
}
}
