Selection Sort

Selection sort is a sorting algorithm that has a quadratic running time complexity of O(n2), thereby making it inefficient to be used on large lists. Although selection sort performs worse than insertion sort algorithm, it is noted for its simplicity and also has performance advantages over more complicated algorithms in certain situations. Selection sort is generally used for sorting files with very large objects (records) and small keys.

Consider an array ARR with N elements. Selection sort works as follows :-

First find the smallest value in the array and place it in the first position. Then, find the second
smallest value in the array and place it in the second position. Repeat this procedure until the
entire array is sorted. Therefore,

• In Pass 1, find the position POS of the smallest value in the array and then swap ARR[POS] and ARR[0]. Thus, ARR[0] is sorted.
• In Pass 2, find the position POS of the smallest value in sub-array of N–1 elements. Swap ARR[POS] with ARR[1]. Now, ARR[0] and ARR[1] is sorted.
• In Pass N–1, find the position POS of the smaller of the elements ARR[N–2] and ARR [N–1]. Swap ARR[POS] and ARR[N–2] so that ARR[0], ARR[1], …, ARR[N–1] is sorted.

Sort the array given below using selection sort.

** Algorithm for selection sort **

	Step 1: Repeat steps 2 and 3 varying j from 0 to n – 2
	Step 2: Find the minimum value in arr[j] to arr[n – 1]:
			a. Set min_index = j
			b. Repeat step c varying i from j + 1 to n – 1
			c. If arr[i] < arr[min_index]:
			      i.   min_index = i
	Step 3: Swap arr[j] with arr[min_index]

Complexity of Selection Sort

Selection sort 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. Therefore,

(n – 1) + (n – 2) + … + 2 + 1
= n(n – 1) / 2 = O(n2)comparisons

					*******************
					Programming Example
					*******************

1. Write a program to sort an array using selection sort algorithm.

#include<stdio.h>
#include<conio.h>

void read(int a[],int n);
void print(int a[],int n);
void shellsort(int a[], int n);

void main()
{
	int a[100],n;
	clrscr();
	printf("\n\n\t Enter of element...>");
	scanf("%d",&n);
	read(a,n);
	print(a,n);
	shellsort(a,n);
	getch();
}

void read(int a[],int n)
{
	int i;
	for(i=0;i<n;i++)
	{
	  printf("\n\n\t array of element...>");
	  scanf("%d",&a[i]);
	}
}

void print(int a[],int n)
{
	int i;
	for(i=0;i<n;i++)
	{
	  printf("\n\n\t array of element...>%d",a[i]);
	}
}

void shellsort(int a[],int n)
{
	int i,k,j,tmp;
	for(i=n/2;i>0;i=i/2)
	{
		for(j=i;j<n;j++)
		{
			for(k=j-1;k>=0;k=k-i)
			{
				if(a[k+i]>=a[k])
				{
				   break;
				}
				else
				{
					tmp=a[k];
					a[k]=a[k+i];
					a[k+i]=tmp;
				}
			}
		}
	}
       print(a,n);
}