Thursday, 3 March 2016

Selection Sort in C++

Leave a Comment
Selection sort is one of the basic algorithms for sorting data, its simplicity proves useful for sorting small amounts of data. Selection sort works by first starting at the beginning array (index 0) and traverses the entire array comparing each value with the current index, if it is smaller than the current index than that index is saved. Once the loop has traversed all the data and if a smaller value than the current index was found a swap is made between the current index in the index where the smaller value was found. The current index is then incremented, now to index 1, the algorithm repeats. Of course, a visual representation is usually more useful. Take an unsorted array that holds five integers.
There are three main variables in selection sort, the variable 'i' keeps the index that may be potentially switched if a smaller value is found. The variable 'j' traverses through the array searching for a value smaller than 'min'. The variable 'min' is the current smallest value in the array, it's updated only if a value smaller than it is found.
selectionsort
Since 'min' always receives the value of index 'i' after every iteration, 'j' can begin one more than 'i'. If index 'j' started at index 'i' then 'min' would be compared with itself obviously there is no need for that. In this algorithm there are two loops, the first loop containing the 'i' variable the second loop within the first loop contains the variable 'j'. For example. 

void selectionSort(int arr[], int size)
{
       for (int i = 0; i < size - 1; i++)//we need to do size-2 passes
       {
             
              for (int j = i + 1; j < size; j++)
              {

              }
       }
}
//where size is the number of elements inside the array

Animation of Selection Sort






Source Code of Selection Sort

#include<iostream>
using namespace std;

void selectionSort(int[], int);//Function Prototype
void main() {
       int arra[5] = { 3,4,1,2,5 };
       selectionSort(arra, 5);
       for (int i = 0; i < 5; i++) {
              cout << arra[i] << endl;
       }
}


void selectionSort(int arr[], int size)
{
       for (int i = 0; i < size - 1; i++)//we need to do size-2 passes
       {
              int iMin = i;
              for (int j = i + 1; j < size; j++)
              {
                     if (arr[j] < arr[iMin]) {
                           iMin = j;
                     }
              }
              //swaping
              int temp = arr[i];
              arr[i] = arr[iMin];
              arr[iMin] = temp;
       }
}

Output:


If You Enjoyed This, Take 5 Seconds To Share It