What is Selection Sort? explain with an example

Selection sort

Selection sort is basically a selection of an element position from the start with the other rest of the elements. Elements are compared and exchanged depending on the condition and then selection position is shifted to the next position till it reaches to the end.

Here are the selection positions of these elements. Comparion takes place with selected position to the rest of the next positions.

Selection sort Big(o)

Selection sort of N elements can take (N - 1) steps and (N - 1) iterations in each steps. Thus resultant is (N-1)*(N-1). This sorting algorithm is not however the best in performance when count of the elements are large. Time complexities of Selection sort is Big(o) = N^2. This sorting is well suited for small number of elements and it is easy the implement in C or any other programming languages.

Selection sort example code

Here is a C source code of Selection sorting with 5 integer elements. This code sorts the elements in ascending order.

 /* Selection sort example */

 #include <stdio.h>

 void swap_node(int *x, int *y)

 {

   int tmp;

   tmp = *x;

   *x = *y;

   *y = tmp;

 }

 void selection_sort(int elements[], int count)

 {

   int select, index;

   printf("Selection sort started-\n");

   for (select = 0; select < count - 1; select++)

   {

     printf("==== Selection %d ====\n", select+1);

     print_array(elements, 5);

     for(index = select + 1; index < count; index++)

     {

       printf("#%d:%d ", select+1, index+1);

       if (elements[select] > elements[index])

       {

         printf("   swap  %d >  %d\n",

                elements[select],

                elements[index]);

         swap_node(&elements[select],

                    &elements[index]);

       } else

       {

         printf("no swap  %d <= %d\n",

                elements[select],

                elements[index]);

       }

       print_array(elements, 5);

     }

   }

   printf("Selection sort ended\n");

 }

 void print_array(int array[], int count)

 {

   int i;

   printf("[");

   for(i = 0; i < count; i++)

   printf("%d, ", array[i]);

   printf("\b\b]\n");

 }

 int main(int argc, char *argv[])

 {

   int array[5] = { 4, 9, 5, 1, 0 };

   printf("Unsorted elements\n");

   print_array(array, 5);

   selection_sort(array, 5);

   printf("Selection sorted elements\n");

   print_array(array, 5);

 }

Steps and Iterations (diagrams)

Output

Unsorted elements                                                                                                                       
[4, 9, 5, 1, 0]                                                                                                                         
Selection sort started-                                                                                                                 
==== Selection 1 ====                                                                                                                   
[4, 9, 5, 1, 0]                                                                                                                         
#1:2 no swap  4 <= 9                                                                                                                    
[4, 9, 5, 1, 0]                                                                                                                         
#1:3 no swap  4 <= 5                                                                                                                    
[4, 9, 5, 1, 0]                                                                                                                         
#1:4    swap  4 >  1                                                                                                                    
[1, 9, 5, 4, 0]                                                                                                                         
#1:5    swap  1 >  0                                                                                                                    
[0, 9, 5, 4, 1]                                                                                                                         
==== Selection 2 ====                                                                                                                   
[0, 9, 5, 4, 1]                                                                                                                         
#2:3    swap  9 >  5                                                                                                                    
[0, 5, 9, 4, 1]                                                                                                                         
#2:4    swap  5 >  4                                                                                                                    
[0, 4, 9, 5, 1]                                                                                                                         
#2:5    swap  4 >  1                                                                                                                    
[0, 1, 9, 5, 4]                                                                                                                         
==== Selection 3 ====                                                                                                                   
[0, 1, 9, 5, 4]                                                                                                                         
#3:4    swap  9 >  5                                                                                                                    
[0, 1, 5, 9, 4]                                                                                                                         
#3:5    swap  5 >  4                                                                                                                    
[0, 1, 4, 9, 5]                                                                                                                         
==== Selection 4 ====                                                                                                                   
[0, 1, 4, 9, 5]                                                                                                                         
#4:5    swap  9 >  5                                                                                                                    
[0, 1, 4, 5, 9]                                                                                                                         
Selection sort ended                                                                                                                    
Selection sorted elements                                                                                                               
[0, 1, 4, 5, 9]