Selection Sort in C++

What is Selection Sort in C++?

Selection sort is another algorithm that is used for sorting i.e. arranging the given data in logical order. This sorting algorithm, iterates through the list and finds the smallest element in the list and swaps it with the first element. And this process is repeated until the list is sorted. In this article, we will learn more about selection sort in C++. This article also contains steps, algorithm and implementation details for the same.

Algorithm of Selection Sort in C++

Steps for Selection Sort in CPP programming

There are following Step of selection sort algorithm in C++.

  • From the  given list find the smallest element.
  • Swap first element in the list with smallest element from the the list.
  • Now exclude the first element and select the smallest element from the remaining list.
  • Now repeat above steps till the list is sorted.

Implementation of Selection Sort

Given below is the implementation detail for selection sort.

  • Set min to the first location i.e. consider the first element in the list is smallest.
  • Search the smallest element in the list.
  • Swap the first location with the smallest value in the list.
  • Assign the second element from the list as min.
  • Repeat the previous steps until we get a the sorted array.
Selection Sort in C++

Algorithm for Selection Sort

  • SelectionSort(Arr[], arr_size):
  • FOR i from 1 to arr_size:
  • min_index = ArrayMinIndex(Arr, i, arr_size)
  • IF i != min_index:
  • swap(Arr[i], Arr[min_index])
  • END of IF
  • END of FOR

Algorithm for finding ArrayMinIndex in sorting process

  • ArrayMinIndex(Arr[], start, end)
  • min_index = start
  • FOR i from (start + 1) to end:
  • IF Arr[i] < Arr[min_index]:
  • min_index = i
  • END of IF
  • END of FOR
  • Return min_index

C++ programming code for selection sort

#include <iostream>
using namespace std;
//Display function to print values. 
void display(int array[], int size) 
{ 
  int i; 
  for (i=0; i < size; i++)
  { 
    cout<<array[i]<<"\t";
  }
  cout<<"\n"; 
} 

//The main function to drive other functions. 
int main() 
{ 
  int array[] = {5, 3, 1, 9, 8, 2, 4, 7}; 
  int size = sizeof(array)/sizeof(array[0]);

  cout<<"Before sorting: \n"; 
  display(array, size);//Using dispaly function to print unsorted array.

  int i, j, min_idx,temp;  
  
    //Loop to iterate elements of array. 
    for (i = 0; i < size-1; i++)  
    {  
        //Here we try to find the min element in array. 
        min_idx = i;  
        for (j = i+1; j < size; j++)
        {
        if (array[j] < array[min_idx])  
            min_idx = j;  
        }
        //Here we interchange the min element with first one.              
        temp = array[min_idx];
        array[min_idx] = array[i]; 
        array[i] = temp;}
        cout<<"After sorting: \n"; 
        display(array, size); //Using dispaly function to print sorted array.
    
    return 0; 
    
}

Selection sort Highlights

Advantages

  • It gives the same time complexity regardless of arrangements of items in the array or data set
  • Since number of operations(swapping, size – 1) are less, so its favorable to use when swapping operations are costly in system

Disadvantages

  • The time complexity is quiet high i.e. O(n2) thus not good
Selection sort in C++ meme

Time Complexity
For Selection Sort

Best

Ω(n2)

Average

Θ(n2)

Worst

O(n2)

Space Complexity

O(1)

Learn to code similar sorting algorithm in C and Java also!