Program For Selection Sort in C++[How to]

Selection Sort

Goal: Sort an Given array using Selection sort.

Method-Used: Selection Sort.

Description: In Selection Sort ,first we find the smallest element in the list and put it in the first position and after that find second smallest element in the list and put it in the second place.

Difference between selection sort and insertion sort ,selection sort only scans as many items as it needs to place the k+1 item at its right place,while selection sort scans all the elements for sort k+1 item.

Selection sort generally used for Small arrays.

Example:

                         2  9  8  4  5

             1st step-2  9  8  4  5

             2nd step- 2  4  8  9  5

             3rd step- 2  4  5  9  8

             4th  step-2  4  5  8  9

                         

Program:-

#include<iostream>

using namespace std;

#include<conio.h>

int min(int b[10],int m,int l)

    {

      int g=b[m],loc=m;

       for(int j=loc+1;j<l;j++)

       {

         if(g>b[j])

           {

               g=b[j];

               loc=j;

           }    

        }   

        return loc;

   }    

     
 int main()

  {

     int a[10],loc,i,temp,n;

     cout<<"\n\tHow many Numbers you want to Enter\n";

     cout<<"\t";

     cin>>n;

    cout<<"\tEnter numbers:\n";

     for( i=0;i<n;i++)

     {

     cout<<"\t";   

     cin>>a[i];

     }
     for(i=0;i<n-1;i++)

      {

        loc=min(a,i,n);

        temp=a[i];

        a[i]=a[loc];

        a[loc]=temp;

     }  

     cout<<"\n\tDisplaying Sorted Elements:\n----";

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

      cout<<"\t";

      cout<<a[i];

      }

      getch();

      return 0;
}   

 Output:

      

 Complexity:

                       As we know in selection sort array is decreased by one element in every pass. i.e. we if number of comparisons in first pass is n then in second pass ,no of comparison will be n-1.

So f(n)=(n-1)+(n-2)+(n-3)+...........+2+1 = n(n-1)/2

                   f(n)=O(n^2)...

 If you want to share more information about topic discussed above or find anything incorrect Please do comments.