Selection Sort

Discussion in 'C' started by rockyrakster, Aug 26, 2009.

  1. rockyrakster

    rockyrakster New Member

    Joined:
    Aug 21, 2009
    Messages:
    26
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Student
    Location:
    Chennai,India

    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: Aug 26, 2009
  2. mayjune

    mayjune New Member

    Joined:
    Jun 14, 2009
    Messages:
    814
    Likes Received:
    33
    Trophy Points:
    0
    Occupation:
    Student
    Location:
    Pune,Delhi
    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)
    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
    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.. :)
     
  3. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    I have moved it to forum because it looks like lots of things need to be worked on before it can qualify as article.
     
  4. pradeep

    pradeep Team Leader

    Joined:
    Apr 4, 2005
    Messages:
    1,645
    Likes Received:
    87
    Trophy Points:
    0
    Occupation:
    Programmer
    Location:
    Kolkata, India
    Home Page:
    http://blog.pradeep.net.in
    It'll nice if the code is well indented with relevant inline commenting.
     
  5. c_user

    c_user New Member

    Joined:
    Aug 23, 2009
    Messages:
    86
    Likes Received:
    8
    Trophy Points:
    0
    Occupation:
    Php dev
    Location:
    Bhubaneswar
    good work frd.
    but avoid goto as said by mayjune...
    it fetch u few marks instead of total...
    use looping.....
    hav a gud day...
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice