The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Sorting

Problem :-
Implement the Selection sort algorithm.

Solution :-
This algorithm is also known as in-place comparison sort algorithm and requires atmost n comparisons for an array with n elements. This algorithm works by finding the smallest element in the unsorted array arr [0 ... n-1] and swapping it with the element in the first position ( index 0 ). Next, we find smallest element in the subarray
arr [1 ... n-1] and swapping it with the element in second position ( index 1 ). We repeat this for rest of the array. This way after n-1 iteration, we get the final sorted array. Complexity of the algorithm is O(n2).
Consider the following array { 7, 2, 5, 3, 4 }. Let's see how Selection sort technique works :-

First Iteration :-
{ 7, 2, 5, 3, 4 } -> { 2, 7, 5, 3, 4 } ( Smallest element found in the array [ 0 ... 4 ] is 2 which is swapped with                                                           element at index 0 i.e 7 )
Second Iteration :-
{ 2, 7, 5, 3, 4 } -> { 2, 3, 5, 7, 4 } ( Smallest element found in the array [ 1 ... 4 ] is 3 which is swapped with                                                           element at index 1 i.e 7 )
Third Iteration :-
{ 2, 3, 5, 7, 4 } -> { 2, 3, 4, 7, 5 } ( Smallest element found in the array [ 2 ... 4 ] is 4 which is swapped with                                                           element at index 2 i.e 5 )
Fourth Iteration :-
{ 2, 3, 4, 7, 5 } -> { 2, 3, 4, 5, 7 } ( Smallest element found in the array [ 3 ... 4 ] is 5 which is swapped with                                                           element at index 3 i.e 7 )

Finally, after four iterations, the array is sorted.

#include<iostream>
using namespace std;

// Display the Array
void displayArray(int arr[], int size) {
   int i;
   for (i=0;i<size;i++) {
      cout<<arr[i]<<" ";
   }
}

// swap elements in the array
void swap(int arr[],int idx1,int idx2) {
   int temp;
   temp = arr[idx1];
   arr[idx1] = arr[idx2];
   arr[idx2] = temp;
}

// selection sort
// select the min element at each iteration and store
// it successively
void selectionSort(int arr[], int size) {
   int i,j;
   // holds the index of min element at the start
   // of each iteration
   int min_idx;
   for (i=0;i<(size-1);i++) {
      // select the minimum element and store
      // it at 'i'th index
      min_idx = i;
      for (j=i+1;j<size;j++) {
         if (arr[min_idx] > arr[j]) {
            // update the min index
            min_idx = j;
         }
      }
      if (min_idx != i) {
         // put the min element in 
         // the index pointed by 'i'
         swap(arr,min_idx,i);
      }
   }
}

// main
int main() {
   int arr[] = {7,4,5,2,3,19,11,6,9,12,8};
   int size = sizeof(arr)/sizeof(arr[0]);
   cout<<"\nOriginal Array :: ";
   displayArray(arr,size);
   selectionSort(arr,size);
   cout<<"\nSorted Array   :: ";
   displayArray(arr,size);
   cout<<endl;
   return 0;
}

Back | Next

All problems on Sorting
* Implement the Bubble Sort algorithm
* Implement the Selection Sort algorithm
* Implement the Insertion Sort algorithm
* Implement the Merge Sort algorithm
* Implement the Quick Sort algorithm