Wednesday, 4 November 2015

C++ Program For Selection Sort Using Function

Problem :- Write A C++ Program For Selection Sort Using Function Also Display The Output Acceding And Descending Order .

Logic :- Step-By-Step Example :-


Here is an example of this sort algorithm sorting five elements:

64 25 12 22 11 // this is the initial, starting state of the array

11 25 12 22 64 // sorted sublist = {11}

11 12 25 22 64 // sorted sublist = {11, 12}

11 12 22 25 64 // sorted sublist = {11, 12, 22}

11 12 22 25 64 // sorted sublist = {11, 12, 22, 25}

11 12 22 25 64 // sorted sublist = {11, 12, 22, 25, 64}

Selection sort animation. Red is current min. Yellow is sorted list. Blue is current item.
(Nothing appears changed on these last two lines because the last two numbers were already in order) .

In Simple Word :- We Store Array First Element to Temporary Variable Call Min and Compare Min To Array Next Element ,If array is Next element is small then Min Become Next smaller element And Swap .Repeat this process until All Element Not Sorted .

Swapping :- 

temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;


Complexity :-


Worst-case performance--> О(n^2)
Best-case performance--> О(n^2)
Average performance-->         О(n^2)
Worst-case space complexity--> О(n) Total, O(1) Auxiliary .

Note :- In All Cases Selection Sort Complexity is Always O(n^2) .

Question :-Why Use Selection Sort When Complexity Is O(n^2) in all Case ?

Answer :- The Best thing about selection sort is it never makes more than O(n) swaps and can be useful when memory write is a costly operation .

Selection Sort Animation :-


Note :- Selection sort animation. Red is current min. Yellow is sorted list. Blue is current item.source Wikipedia

Try This C Program For Insertion Sort

Solution :-



#include <iostream>
using namespace std;

int selectionsort(int arr[],int n);
//Program By Ghanendra Yadav 
int main()
{
    int i,x,n;
    cout<<"Enter The Size Of Array \n";
    cin>>n;
    int arr[n];
    cout<<"Enter The Element Of Array \n";
    for(i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    selectionsort(arr,n);
    return 0;
}

int selectionsort(int arr[],int n)
{
    int i,j,temp,min;
    
    for(i=0;i<n-1;i++)
    {
    min=i;
        for(j=i+1;j<n;j++)
        {
        if(arr[j]<arr[min])
        {
        min=j;
        }
}
        temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp; 
    }
    
    cout<<"\nSORTED ARRAY IN ACCENDING ORDER \n\n";
 
for(i=0;i<n;i++) 
  {
  cout<<arr[i]<<" ";
  }

cout<<"\n\nSORTED ARRAY IN DESCENDING ORDER \n"<<endl;
 
for(i=n-1;i>=0;i--) 
  {
  cout<<arr[i]<<" ";
  }
}

See Also :-


C++ Program For Selection Sort

No comments:
Write comments

Recommended Posts × +