Selection sort explained with simple example

Selection sort is one of the simplest sorting algorithm, which traverse through the list, picks the minimum item from the unsorted list and place it in its place in the final sorted list.
This sorting algorithm contains (n – 1) traversal.

Pros:
1) Simple algorithm and hence efficient for small list of data.
2) No extra memory needed.
3) Good for cases when list is almost sorted (only few misplaced items).
4) Very less number of swap operation(O(n)), as in every pass only 1 swap of data is needed at max.

Cons:
1) Very slow algorithm. Not good for very large set of data.

Algorithm explained via example:

Let us take an example array “7 9 3 12 1”. Now we will run through this array with selection sort algorithm to understand how it works.

First traversal (pick minimum item and swap to 1st place):
{7, 9, 3, 12, 1} –> {1, 9, 3, 12, 7} , Swap operation between 1 and 7.

Second traversal (pick minimum from remaining item):
{1, 9, 3, 12, 7} –> {1, 3, 9, 12, 7} , Swap operation between 3 and 9.

Third traversal (pick minimum from remaining item):
{1, 3, 9, 12, 7} –> {1, 3, 7, 12, 9} , Swap operation between 7 and 9.

Fourth traversal (pick minimum from remaining item):
{1, 3, 7, 12, 9} –> {1, 3, 7, 9, 12} , Swap operation between 12 and 9.

Now the list is sorted.

Let’s have a look at the sample program for Selection sort.

void printArray(int a[] )
{
	for (int i = 0; i < 12; i++)
	{
		cout << a[i] << ", ";
	}
	cout << endl;
}

void selectionSort()
{
	int a[] = { 76,4,65,33,23,10,44,38,97,100,1,59 };
	cout << "Selection Sort" << endl;
	cout << "Initial array" << endl;
	printArray(a);

	for (int i = 0; i &lt; 12; i++)
	{
		int pos = i;
		for (int j = i; j &lt; 12; j++)
		{
			if (a[j] &lt;= a[pos])
			{
				pos = j;
			}
		}
		int temp = a[pos];
		a[pos] = a[i];
		a[i] = temp;
	}

	cout << "Sorted array" << endl;
	printArray(a);
}

int main()
{
    selectionSort();
}

Output of the above program is as follows:

Selection Sort
Initial array
76, 4, 65, 33, 23, 10, 44, 38, 97, 100, 1, 59,
Sorted array
1, 4, 10, 23, 33, 38, 44, 59, 65, 76, 97, 100,

Algorithm performance:

Time complexity:
Selection sort is not affected by data distribution. Hence, total number of comparison needed are (1+ 2 + … + (n – 1) + n).
Hence, time complexity for best and worst both case scenario is O(n*n).

Space complexity:
Since, no extra space is needed for this sorting algorithm. Hence, Space complexity is O(1).