Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   Selection Sort (http://www.go4expert.com/forums/selection-sort-t19181/)

rockyrakster 26Aug2009 17:43

Selection Sort
 

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


mayjune 27Aug2009 01:58

Re: Selection Sort
 
Nice code, Few things

1) You used GOTO, avoid using GOTO, whether its for college or otherwise (in fact specially for college as your teachers will blast at you no matter what the reason is, do not use GOTO. One of my friend used this in the test, he Got 20/50 just because he used GOTO otherwise his code was good to get above 35 atleast...So you can imagine.)

2)
Quote:

"I have found his all important line mssing in many standard books "
English mistakes (ask any mod to correct it if you can't, and second instead of saying that say why you added it, I haven't seen the code but it would be nice if you give some brief account of what the line/function is about wherever necessary and what the variables are for so the idea of the code is more clear to the newbies.
Also instead of saying
Quote:

"The Line I added in the code from standard code makes it more efficient for longer arrays"
Say, by adding this the code gets efficient in this way, and If i don't use this line this is what happens. This will not only make us appreciate about it, newbies will understand your code more easily... :)

3)
Code:

    for(k=0;k<size;k++)
 cout<<a[k]<<" ";
      cout<<"\n";

Since you didn't use { } the, for loop is only for first cout, but the identation may confuse the newbies, as selection sort is one of the basics, This thread will be checked by people who are newbies in C++. Thus from that idea, make things more clearer so that they don't get confused about it..

Nice effort...Post more.. :)

shabbir 27Aug2009 10:02

Re: Selection Sort
 
I have moved it to forum because it looks like lots of things need to be worked on before it can qualify as article.

pradeep 27Aug2009 10:44

Re: Selection Sort
 
It'll nice if the code is well indented with relevant inline commenting.

c_user 30Aug2009 06:11

Re: Selection Sort
 
good work frd.
but avoid goto as said by mayjune...
it fetch u few marks instead of total...
use looping.....
hav a gud day...


All times are GMT +5.5. The time now is 00:28.