Selection Sort

Selection sort is a sorting algorithm in which the smallest element is found and placed at a[0], then the second smallest element is placed at a[1] and this advances till the (n-1) elements.

It is generally not very efficient in dealing with large arrays and has a O(n^2) time complexity. Time complexity is the time taken by an algorithm to run depending on the input given.

Incase you are still not at a level of understanding time complexities, do not worry, the rest is basic.

Algorithm


This is how selection sort works:

  1. Find the smallest number of the list, place it at a[0]
  2. Repeat the steps for the second smallest number and place it at a[1]
  3. Advance for the other elements of the list similarly.

Explanation


Let’s take an example integer array as follows:

23 45 11 21 56 92 24 62

We’ll have a integer variable called small which stores the smallest value for each iteration and pos will store its position.

The first element’s value is stored in small to begin with. Now, we will travel through the entire array to see if there is any other element which is smaller than the first one. If there is, swap them else leave them as it as.

After first iteration, the array, we had above would look like this:

11 45 23 21 56 92 24 62

Then, we will advance similarly by finding the second smallest number and swapping it at a[1] (the second position in the array, as we start our index from 0).

11 21 23 45 56 92 24 62

Each iteration is called a PASS and the rest of the PASSES for the array above are as follows:

11 21 23 45 56 92 24 62
11 21 23 24 56 92 45 62
11 21 23 24 45 92 56 62
11 21 23 24 45 56 92 62
11 21 23 24 45 56 62 92 
11 21 23 24 45 56 62 92  --> The final sorted array

Final Source Code in C++/C


Toggle over the language to view the source code in C++ and C respectively.


 

#include <iostream.h>
void main()
{
	int a[10], temp, small, pos, i,j;
//Input array elements
	for(i=0; i<10;i++)
	{
		cin>>a[i];
	}
// Start sorting
	for (i=0; i< 9;i++)
	{
		small=a[i];
		pos=i;
		for(j=i;j<10;j++)
		{
			if(a[j] < small)
			{
				small=a[j];
				pos=j;
			}
		temp=a[i];
		a[i]=small;
		a[pos]=temp;
	}
// Print sorted array
	for(i=0; i < 10;i++)
	{
		cout<<a[i];
	}
}


 

#include <stdio.h>
#include <conio.h>
void main()
{
	int a[10], temp, small, pos, i,j;
//Input array elements
	for(i=0; i<10;i++)
	{
		scanf("%d", &a[i]);
	}
// Start sorting
	for (i=0; i< 9;i++)
	{
		small=a[i];
		pos=i;
		for(j=i;j<10;j++)
		{
			if(a[j] < small)
			{
				small=a[j];
				pos=j;
			}
		temp=a[i];
		a[i]=small;
		a[pos]=temp;
	}
// Print sorted array
	for(i=0; i<10;i++)
	{
		printf("%d", a[i]);
	}
}