Selection sort is one of the simple sorting algorithms with time complexity O(n2).
How selection sort works
In selection sort, first, we search for a minimum number, then put it on the first index.
Then in the second iteration, we search for the second minimum and put it on the second index.
Thus we do the same for every index.
Let an array is 4, 2, 3, 5, 1 and it is a zero-based indexed
For the first iteration, 4, 2, 3, 5, 1
Find the minimum number from the 0th index to the 4th index inclusive.
For the minimum number on the 4th index, swap the 4th number with the 0th number.
After the first iteration array looks like 1, 2, 3, 5, 4
For the second iteration, 1, 2, 3, 5, 4
Find the minimum number from 1st to 4th position. Then swap it with 1st element.
After 2nd iteration array looks like 1, 2, 3, 5, 4
For the 3rd iteration 1, 2, 3, 5, 4
The minimum number is in 2nd index,
After 3rd iteration, 1, 2, 3, 5, 4
For 4th (final in this case) iteration 1, 2, 3, 5, 4
The minimum number is in the 4th index, swap the 3rd number with the 4th number. After 4th iteration, the array is sorted and looks like 1, 2, 3, 4, 5
Here, the Time complexity of finding the minimum element is O(n). And we will do it n times.
So, the time complexity is O(n2).
Selection sort using c
#include <stdio.h>
int main() {
int arr[5]={4, 2, 3, 5, 1};
for(int i=0;i<5-1;i++)
{
int mnidx=i;
for(int j=i+1;j<5;j++)
{
if(arr[mnidx]>arr[j]) mnidx=j;
}
int tmp=arr[i];
arr[i]=arr[mnidx];
arr[mnidx]=tmp;
}
for(int i=0;i<5;i++)
{
printf("%d ", arr[i]);
}
return 0;
}
Selection sort using c++
#include <bits/stdc++.h>
using namespace std;
int main() {
int arr[5]={4, 2, 3, 5, 1};
for(int i=0;i<5-1;i++)
{
int minIndex=i;
for(int j=i+1;j<5;j++)
{
if(arr[minIndex]>arr[j]) minIndex=j;
}
swap(arr[minIndex], arr[i]);
}
for(int i=0;i<5;i++)
{
cout<<arr[i]<<" ";
}
return 0;
}
Selection sort using python
arr=[4, 2, 3, 5, 1]
for i in range(len(arr)):
minIndex=i;
for j in range(i+1, len(arr)):
if(arr[minIndex]>arr[j]):
minIndex=j
arr[minIndex], arr[i]=arr[i], arr[minIndex]
print(arr)
Selection sort using Java
import java.util.*;
class Sort{
public static void main(String[] args) {
int[] arr={4, 2, 3, 5, 1};
for(int i=0;i<5;i++)
{
int minIndex=i;
for(int j=i+1;j<5;j++)
{
if(arr[j]<arr[minIndex])
{
minIndex=j;
}
}
int tmp=arr[i];
arr[i]=arr[minIndex];
arr[minIndex]=tmp;
}
System.out.println(Arrays.toString(arr));
}
}
Selection sort Using Javascript
var arr=[4, 2, 3, 5, 1];
for(var i=0;i<5;i++)
{
var minIndex=i;
for(var j=i+1;j<5;j++){
if(arr[j]<arr[minIndex])
{
minIndex=j;
}
}
[arr[i], arr[minIndex]]=[arr[minIndex], arr[i]];
}
console.log(arr)