AppDividend
Latest Code Tutorials

Selection Sort In C++ Tutorial With Example | C++ Selection Sort Program

2

Selection Sort In C++ Tutorial With Example | C++ Selection Sort Program is today’s topic. Like Bubble Sort, Selection Sort is also a sorting algorithm; especially it is an in-place comparison sort. Selection sort algorithm is based on an idea of finding the min or max element or item in the unsorted array and then putting it in its correct position in the sorted array.

Selection Sort In C++ Tutorial

Selection sort algorithm divides an array into two parts:

  1. A sorted subarray
  2. The unsorted sub-array, from where we have to pick the smallest element and then put it into the sorted array.

Selection sort is a very simple sorting algorithm. A selection sorting algorithm is an in-place comparison-based algorithm in which the list or an array is divided into two parts, the sorted part at the leftmost end and the unsorted part at the right most end. So, initially, the sorted part is empty, and the unsorted part is an entire list.

The smallest element is selected from an unsorted array and swapped with the leftmost element, and that element becomes the part of a sorted array. This process continues moving unsorted array boundary by the component to the right. Finally, we get the sorted values.

We will first see the algorithm, and then we will see an example of Selection Sort.

Algorithm of Selection Sort:

Selection(A,N)

Step1: Repeat step 2 and 3 for (k=0;k<n-1;k++)

Step2: Call MINIMUM(A,K,N,LOC)

Step3: Swap A[K] and A[LOC]

Step4: Exit

MINIMUM(A,K,N,LOC)

Step1: Set min=A[K] and LOC=K

Step2: Repeat step 3 and 4 for(i=k;i<n;i++)

Step3: if min>a[i]

Step4: set min=a[i] and LOC=i

Step5: Return LOC

Explanation with an example

So, from the algorithm what we can understand that, as said above the array is in two parts, one part is in sorted order, and another part is in unsorted order and from that unsorted order, we are finding the smallest value and putting it into sorted order list.

For example, Let’s take a list of integer:

Array Number 12 10 86 4 13
Location 0 1 2 3 4

 

First Pass:

When K=0; SELECTION() will call MINIMUM() and will check the smallest value from the list. So, here in the first pass, the lowest value will be 4, and the MINIMUM() will return the location of 4 that is LOC=3.

Then, SELECTION() will swap the value with current A[0]=12. So, after swapping the value new array will be:

Array Number 4 10 86 12 13
Location 0 1 2 3 4

 

Second Pass:

Now, K=1 and again SELECTION() will call MINIMUM() and the then it will check the smallest value from the unsorted array, that is 10 and then it will return the location of 10, i.e., LOC=1.

As 10 is at its correct position so the final array will be the same as it is.

Third Pass:

Now, K=2 and again SELECTION() will call MINIMUM() and the then it will check the smallest value from the unsorted array, that is 12, and then it will return the location of 12, i.e., LOC=3.

Then, SELECTION() will swap the value with current A[2]=86. So, after swapping the value new array will be:

Array Number 4 10 12 86 13
Location 0 1 2 3 4

Fourth Pass:

Now, K=3 and again SELECTION() will call MINIMUM() and the then it will check the smallest value from the unsorted array, that is 13, and then it will return the location of 13, i.e., LOC=4.

Then, SELECTION() will swap the value with current A[3]=86. So, after swapping the value new array will be:

Array Number 4 10 12 13 86
Location 0 1 2 3 4

 

Selection Sort Pseudocode

procedure selection sort 
   list  : array of items
   n     : size of list

   for i = 1 to n - 1
   /* set current element as minimum*/
      min = i    
  
      /* check the element to be minimum */

      for j = i+1 to n 
         if list[j] < list[min] then
            min = j;
         end if
      end for

      /* swap the minimum element with the current element*/
      if indexMin != i  then
         swap list[min] and list[i]
      end if
   end for
	
end procedure

C++ Program of Selection Sort

See the below code of the selection.cpp.

#include<bits/stdc++.h>
using namespace std;

int minimum(int a[],int n, int k, int loc)
{
	loc=k;
	int min=a[k];
	for(int i=k;i<n;i++)
	{
		if(a[i]<min)
		{
			min=a[i];
			loc=i;
		}
	}
	return loc;
}
int selection(int a[],int n)
{
	int loc=-1,k;
	for(k=0;k<n-1;k++)
	{
		int loc1=minimum(a,n,k,loc);
		int temp=a[k];
		a[k]=a[loc1];
		a[loc1]=temp;
	}
	cout<<"The sorted list is:\n";
	for(k=0;k<n;k++)
	cout<<a[k]<<" ";
}
int main()
{
	int n;
	cout<<"Enter the size of the array: ";
	cin>>n;
	int a[n],i;
	cout<<"Enter the array values:\n";
	for(i=0;i<n;i++)
	{
		cin>>a[i];
	}
	//calling selection function
	selection(a,n);
	return 0;
}

Output:

Selection Sort In C++ Tutorial With Example | C++ Selection Sort Program

 

Time Complexity:

If we want to find the minimum element from the array of N elements, N−1 comparisons are required. After putting the minimum item in its proper position, the size of an unsorted array reduces to N−1, and then N−2 comparisons are necessary to find the minimum in the unsorted array.

Therefore (N−1) + (N−2) + ……. + 1 = (N⋅(N−1))/2 comparisons and N swaps result in the overall complexity of O(N2).

So, the time complexity for selection sort is O(n2) as there are two nested loops.

Auxiliary Space: O(1)

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

Conclusively, Selection Sort In C++ Tutorial With Example | C++ Selection Sort Program is over.

2 Comments
  1. Abid Ghori says

    This Post explains everything is detail about the selection sort algorithm.. Thanks alot dear. great work..!

  2. Abid Ghori says

    Keep it up.. thanks again!

Leave A Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.