Selection Sort is a simple sorting algorithm which sorts a list of values by dividing the list into parts - sorted and unsorted, and selecting the minimum value from the unsorted list and placing it in the sorted one. We will now discuss the algorithm of selection sort, how it works, its advantages and disadvantages, its implementation in C along with its complexity analysis.
The Algorithm
function selection_sort(int arr[], int N)
{
/* input is an array of elements
array indexing is from 0 to N-1, where N is the size of array
*/
for ( i = 0 to N-1 )
min_index = i
for j = i to N-1
find index of minimum element in remaining list
end inner for loop
swap current position with minimum element
end outer for loop
}
How it works
 |
An illustration of how the selection sort works
Image source : en.wikipedia.org |
Its working is quite simple. The list is divided into two small lists - sorted and unsorted. Initially, the sorted list is empty and the unsorted list contains all the elements. Now, select the minimum element from the unsorted list and insert it into the sorted list. Again, select minimum element from unsorted list and append it into the sorted list. Continue till you have no elements left in the unsorted list. Let's take an example to make it clear :
Consider an array : { 2 4 3 5 1 }
First step : { 1 4 3 5 2 }
Second step : { 1 2 3 5 4 }
Third step : { 1 2 3 4 5 }
Fourth step : { 1 2 3 4 5 }
Advantages and Disadvantages of Selection Sort
1. It has a very simple implementation.
2. It is efficient for small size of input data.
3. It is more efficient than bubble sort.
4. Its has very low space complexity - requires only single extra memory space.
5. It is inefficient for large data sets - it has a time complexity of O(n^2).
Complexity Analysis
 |
Animation of the selection sort
Image source : en.wikipedia.org |
Worst - case time complexity : O(n^2)
Best - case time complexity : O(n^2)
Average - case time complexity : O(n^2)
Space complexity : O(1) - for extra memory , O(n) - for storing the list
Implementation in C
#include <stdio.h>
#include <stdlib.h>
void selection_sort(int a[],int n)
{
int i,j,temp=0,min_index=0;
for(i=0;i<n;i++)
{ min_index = i;
for(j=i;j<n;j++)
{
if(a[j]<a[min_index])
min_index = j;
}
{
temp = a[i];
a[i] = a[min_index];
a[min_index] = temp;
}
}
printf("sorted array:");
for(i=0;i<n;i++)
printf(" %d ",a[i]);
}
int main()
{ int n,i;
int arr[10];
printf("enter size of array: ");
scanf("%d",&n);
printf("enter the array: ");
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
selection_sort(arr,n);
return 0;
}
