Arrange the array elements in ACS order using "Selection Sort".
Objective
Write a C++ program to sort an array using Selection Sort.
Algorithm / Approach
- Initialize an unsorted array.
- Run an outer loop
ifrom 0 up tosize - 1. - Run an inner loop
jstarting immediately afteri(j = i + 1) to the end. - Compare the element at
iagainst every element atj. - If
ar[i] > ar[j], swap them immediately. - Print the fully sorted array.
main.cpp
#include<iostream>
using namespace std;
int main(){
int i,j,temp;
int ar[5] = {25,17,31,13,2};
cout<<"BEFORE SORTING :\n";
for(i=0; i < 5; i++) {
cout<< ar[i]<<" ";
}
for(i=0; i < 5-1;i++){
for(j=i+1; j < 5; j++){
if(ar[i]>ar[j]){
temp=ar[i];
ar[i]=ar[j];
ar[j]=temp;
}
}
}
cout<<"\n\nAFTER SORTING :\n";
for(i=0; i < 5; i++) {
cout<< ar[i]<<" ";
}
return 0;
}Expected Output
BEFORE SORT : 25 17 31 13 2 AFTER SORT : 2 13 17 25 31
Explanation of the Program
- Selection Sort divides the array into a sorted portion and an unsorted portion. It continuously scans the unsorted portion, selects the smallest element it can find, and swaps it into the sorted portion.
- Note on the provided code: This implementation eagerly swaps the elements the moment it finds a smaller one. A more optimized standard Selection Sort will just record the *index* of the minimum value during the inner loop, and then perform exactly ONE single swap at the end of the outer loop.
Complexity
Time Complexity
O(n^2)
Space Complexity
O(1)
