Tuesday, 12 September 2017

Implementation of Selection Sorting in C++

The selection sort algorithm construct the sorted sequence one element at a time, by adding elements to the sorted sequence in order. At each step, the next element to be added to the sorted sequence is selected from the remaining elements. Because the elements are added to the sorted sequence in order, they are always added at one end. This makes the selection sorting different from the insertion sorting. In insertion sorting, the element are added to the sorted sequence in an arbitrary order. Therefore, the position in the sorted sequence at which each subsequent element is inserted is arbitrary. Both selection and insertion sorts sort the array in-place.     
In this method, we sort a set of unsorted elements in two steps. 
In the first step, find the smallest element in the structure.  
In the second step, swap the smallest element with the element at the first position. Then, find the next smallest element and swap with the element at the second position.
Repeat these steps until all elements get arranged at proper positions. 

Implementation of Selection Sorting in C++

//  Selection sorting

#include <iostream>
using namespace std;


// definition of function where logic of selection method is implemented.

void select_sort(int arr[],int n)
{
    int i;
    for(i=0;i<n;i++)
    {
        int flag=0;
        int temp=0,pos,no = arr[i];
        for(int j=i+1;j<n;j++)
        {
            if(arr[j]<no)
            {
                no = arr[j];
                pos = j;
                flag=1;
            }
        }



        if(flag==1)
        {
            temp = arr[i];
            arr[i] = arr[pos];
            arr[pos] = temp;
        }
    }
}

//  main function with function call
int main() 

{
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
        cin>>arr[i];
    select_sort(arr,n);
    for(int i=0;i<n;i++)
        cout<<arr[i]<<" ";
    return 0;
}



Selection sorting is a sorting algorithm that is independent of the original order of elements in the array. 
In Pass 1. selecting the element with the smallest value calls for scanning all n elements; thus n-1 comparisons are required in the first pass. Then, the smallest value is swapped with the element in the first position. 
In Pass 2. Selecting the second smallest value requires scanning the remaining n-1 elements and so on.


Thanks
Mukesh Rajput

No comments:

Post a Comment

Thanks
Mukesh Rajput