C++ Program - Selection Sort

Selection sort is based on the idea of finding smallest or largest element in unsorted array and placing it at the correct position in the sorted array. This will result into increasing the length of the sorted array by one and decreasing the length of unsorted array by one after each iteration.

Example:

To understand the selection sort, lets consider an unsorted array [1, 10, 23, -2] and discuss each step taken to sort the array in ascending order. In every pass, smallest element is found in the unsorted array and swapped with first element of unsorted array.

First Pass: The whole array is unsorted array and (-2) is the smallest number in the array. After finding (-2) as smallest number, it is swapped with first element of the array.

Second Pass: In this example, the left hand side array is sorted array and length of this array increase by one after each iteration. After first pass length of the sorted array is one. Rest of the array is unsorted array. (1) is the smallest number in the unsorted array which is swapped with first element of the unsorted array. After this swap, length of the sorted array and unsorted array will be two.

Third Pass: (10) is the smallest number in the unsorted array and swapped with the first element of the unsorted array.

Fourth Pass: (23) is the only number in the unsorted array and found to be at the correct position.

Implementation of Selection Sort

#include <iostream>
using namespace std;

// function for selection sort
static void selectionsort(int Array[], int n) {
  int temp;
  for(int i=0; i<n; i++) {
    int min_idx = i;
    for(int j=i+1; j<n; j++) {
      if(Array[j] < Array[min_idx])
      {min_idx = j;}
    }
    temp = Array[min_idx];
    Array[min_idx] = Array[i];
    Array[i] = temp;
  }
}

// function to print array
static void PrintArray(int Array[], int n) { 
  for (int i=0; i<n; i++)  
    cout<<Array[i]<<" "; 
  cout<<"\n"; 
} 

// test the code
int main (){
  int MyArray[] = {1, 10, 23, 50, 4, 9, -4};
  int n = sizeof(MyArray) / sizeof(MyArray[0]); 
  cout<<"Original Array\n";
  PrintArray(MyArray, n);

  selectionsort(MyArray, n);
  cout<<"\nSorted Array\n";
  PrintArray(MyArray, n);
  return 0;
}

The above code will give the following output:

Original Array
1 10 23 50 4 9 -4 

Sorted Array
-4 1 4 9 10 23 50

Time Complexity:

The time complexity of selection sort is Θ(N²) in all cases even if the whole array is sorted because the entire array need to be iterated for every element and it contains two nested loops.