Selection Sort in C, C++, Java with Examples | FACE Prep

In this article, we will be discussing everything about Selection sort – Selection sort algorithm, Selection sort program in C, C++, Java, Selection sort time complexity etc.

Prerequisite: Bubble Sort Algorithm

What is Selection sort?

A Selection sort algorithm sorts an array of elements by iterating and finding the smallest/largest one and then putting it aside into a sorted list. It continues to sort by finding the smallest/largest unsorted element and adding it to the sorted list of elements. This happens until there are no elements left in the unsorted list.

selection sort in c

Selection Sort Example

Assume that the array A = [14,16, 3, 6, 50] needs to be sorted in ascending order.

So now, the minimum element in the array i.e. 3 is searched for and then swapped with the element that is currently located in the first position, i.e. 14. Now the minimum element in the remaining unsorted array is searched for and put in the second position, and so on. Have a look at the implementation explained below.

selection sort in c

Selection Sort Pseudo code

for i = 0 to n - 1
// Finding the minimum element in unsorted array
min = i
for j = i + 1 to n
if arr[j] < arr[min] then
min = j
end if
end for
// Swapping the found minimum element with the first element
swap(arr[min], arr[i])
end for

Selection Sort in C, C++, Java Implementation

Here is the implementation of selection sort in various languages.

#include<stdio.h>
int main()
{
int n, i, j, temp, min;
scanf("%d", &n);
int arr[n];
for(i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
for (i = 0; i < n - 1; i++)
{

// Finding the minimum element in unsorted array

min = i;
for (j = i + 1; j < n; j++)
if (arr[j] < arr[min])
min = j;

// Swaping the found minimum element with the first element

temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
for(i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}
#include<iostream>
using namespace std;
int main()
{
int n, i, j, temp, min;
cin >> n;
int arr[n];
for(i = 0; i < n; i++)
{
cin >> arr[i];
}
for (i = 0; i < n - 1; i++)
{

// Finding the minimum element in unsorted array

min = i;
for (j = i + 1; j < n; j++)
if (arr[j] < arr[min])
min = j;

// Swaping the found minimum element with the first element

temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
for(i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
}
import java.util.Scanner;
public class Main
{
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int i, j, temp, min;
int n = sc.nextInt();
int arr[] = new int[n];
for(i = 0; i < n; i++)
{
arr[i] = sc.nextInt();
}
for (i = 0; i < n - 1; i++)
{
// Finding the minimum element in unsorted array
min = i;
for (j = i + 1; j < n; j++)
if (arr[j] < arr[min])
min = j;
// Swaping the found minimum element with the first element
temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
for(i = 0; i < n; i++)
{
System.out.print(arr[i] + " ");
}
}
}

Input:

4 (Number of elements)
33 76 21 2

Output: 

2 21 33 76

Time Complexity of Selection Sort

To find the smallest element from the array of n elements,  n−1 comparisons are required. After putting the smallest element in the sorted array list, the size of an unsorted array reduces to n−1 and then n−2comparisons are required to find the next 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).

Selection Sort Vs Bubble Sort

ParameterSelection sortBubble sort
EfficiencyImproved efficiency as compared to bubble sortInefficient due to a large number of comparisons to be made in each iteration
Best case time complexityO(N2). In Selection sort, we cannot identify if the array is sorted or not within the 1st iteration.O(n). In Bubble sort, we can identify whether a list is sorted within the 1st iteration.
StabilityUnstableStable

Also See Similar DS Sorting Techniques