Selection Sort in C++

Here we are going to learn how to implement selection sort in C++. Hope you will enjoy learning it.

‘Sorting’ in programming refers to the proper arrangement of the elements of an array (in ascending or descending order).

Note: ‘array’ is a collection of variables of the same data type which are accessed by a single name.

Algorithm of Selection Sort

‘Selection Sort’ uses the following algorithm to  sort the elements of an array:
let the array be -> {4,7,2,1}

  1. Find the smallest (or largest) element for the 1st position of the array to sort in ascending (or descending) order, then swap the position of that element with that of the element at the 1st position
    4<7 -> 2<4 -> 1<2
    hence 1 and 4 are swapped, so array -> {1,7,2,4}
  2. Find the smallest (or largest) element for the 2nd position of the array, ignoring the element at the 1st position, then swap the position of that element with that of the element at the 2nd position
    2<7 -> 2<4
    hence 2 and 7 are swapped, so array -> {1,2,7,4}
  3. Similarly, find the smallest (or largest) element for the ith position of the array, ignoring the elements before the ith position (note: ‘i’ takes values up till the length of the array), then swap the position of that element with that of the element at the ith position
    4<7
    hence 4 and 7 are swapped, so array -> {1,2,4,7}
    Thus, the sorted array is -> {1,2,4,7}

C++ Code for selection sort

#include <stdio.h>
#define size 4 //pre-defining the array length for the program
void inputArray(int array[],int length)
 {
     printf("Input %d (integer) elements: ",length);
     //note, in the for loop, the intitializing statement is decreasing the value of length by 1 because in arrays, counting starts from 0
     for(length--;length>=0;length--){
        scanf("%d",&array[length]);
     }
 }
//logic for selection sort - finding the smallest element for the first position, the second smallest for the second position, ...., the largest element for the last position
void selectionSort(int array[],int length)
 {
//note, at every 'i' iteration of the first for-loop, the elements before position 'i' are already sorted, so the second for loop starts at position 'i+1'
     for(int i = 0; i < length-1; i++){
        int position = i;
        for(int j = i+1; j < length;j++)
            if(array[j]<array[position])position=j;
        //if there is no element after position 'i' which is smaller than the element at position 'i', then there is no need to swap
        if(position==i)continue;
        array[i]+=array[position];
        array[position]=array[i]-array[position];
        array[i]-=array[position];
     }
 }
void printArray(int array[],int length)
 {
     printf("The elements of the given array are: ");
     for(int i=0;i<length;i++)printf("%d ",array[i]);
 }
int main()
{
    int array[size];//creating an integer array
    inputArray(array,size);//taking input in the array
    selectionSort(array,size);//sorting the array with the desired sorting algorithm
    printArray(array,size);//printing the array after sorting
    return 0;
}

Output:




Input 4 (integer) elements: 4 7 2 1
The elements of the given array are: 1 2 4 7

Summary:

  • inputArray(int[],int) is called to take input integer elements from the user and store them in the array
  • selectionSort(int[],int) is called to sort the elements of the array with the algorithm explained above
  • printArray(int[],int) is called to print the elements of the array (after sorting)

Note:

  • the value ‘4’ after size can be changed to any other value in order to get the desired array-length
  • since (in C++) arrays are passed by reference, therefore the changes made in selectionSort(int[],int) stay permanently
  • to sort in descending order, just change the sign from ‘<’ to ‘>‘ in the logical condition inside the 2nd for loop

Also read:


Leave a Reply

Your email address will not be published. Required fields are marked *