In this tutorial, you will learn how a selection sort works. It is a simple sorting algorithm. Also, we have implemented Selection sort technique in C++.
Procedure of selection sort
- Set the first element as minimum.
- Compare minimum to each element starting from second. If any element is smaller, assign it to minimum.
- Swap first element with the minimum element.
- Loop the first 3 steps for all the elements.
Time Complexity
- Worst Case – O(n^2)
- Average Case – O(n^2)
- Best Case – O(n^2)
Space Complexity – O(1)
The code is implemented in C++ here
#include<iostream>
using namespace std;
void print(int a[],int size){
cout<<"The elememts are "<<endl;
for(int i=0;i<size;i++){
cout<<a[i]<<" ";
}
cout<<endl;
}
void selection_sort(int a[], int size){
int i,j,min_id;
for(i=0;i<size;i++){
min_id = i;
for(j=i+1;j<size;j++){
if(a[j]<a[min_id]) min_id = j;
}
swap(a[i],a[min_id]);
}
return;
}
int main(){
int a[]={10,9,50,23,27,32,65,89,30};
int size = sizeof(a)/sizeof(int);
print(a,size);
selection_sort(a, size);
print(a,size);
return 0;
}
