What is Selection Sort? explain with an example

Selection sort

Selection sorting is done by selecting an element position from the start of the collection and then finding the lowest(or highest) from the rest of the group of elements. These two selected elements are compared and swapped based on the condition. This same logic is repeated for the rest of the element positions one after another till the iteration cycle reaches the end of the collection. The name selection sort came since the lowest(or highest) element is selected among the collection and it is compared and exchanged with the positioned element.

Algoritm and Pseudo code

Here is the basic algorithm steps-

Selection Loop Start with 1st Element (I = 0).
Select the I th Element.
Find least element in the range (I + 1 to N).
Compare and Swap I th position with least element.
If I < (N - 1) goto step #2.

Here is the basic logic and steps of finding the least item-

Least item is 1st Element (I = 0).
Select the I th Element.
If I th Element < Least item; then Least item = I th Element;
If I < N goto step #2.
Return Index of Least item;

Selection sort visualization

Here the selection algorithm can be visualized with the first element then the next element and it goes till the last element. Each time one element is selected it belongs to the sorted left group. The elements in the right side group are the unsorted group. A search is performed to find the least or the highest element in the unsorted group. This element is interexchanged to the sorted group. The sorted group increases as the iteration moves towards the right and more elements are selected and inter exchanged from the right side group. Finally, the algorithm stops at the last element as it is compared with the previous to the last element.

Selection sort C code

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

 #include <stdio.h>

 void swap_node(int *x, int *y)

 {

   int tmp;

   tmp = *x;

   *x = *y;

   *y = tmp;

 }

 int find_least(int elements[], int count, int pos)

 {

   int index, value, minindex;

   value = elements[pos];

   minindex = pos;

   for(index = pos; index < count; index++)

   {

       if (elements[index] < value) {

           value = elements[index];

           minindex = index;

       }

       printf("%d ", elements[index]);

   }

   return minindex;

 }

 void selection_sort(int elements[], int count)

 {

   int select, index, value, minindex;

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

   /* Select one element position from left group */

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

   {

     value = elements[select];

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

     print_array(elements, 5);

   /* Select the smallest element from the right group */

     minindex = find_least (elements, count, select + 1);

     if (elements[minindex] < elements[select])

     {

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

                elements[minindex],

                elements[select]);

         swap_node(&elements[select],

                    &elements[minindex]);

       } else

       {

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

                elements[minindex],

                elements[select]);

       }

       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) ====
[4, 9, 5, 1, 0] 
9 5 1 0 swap min (0) >  4
[0, 9, 5, 1, 4] 
==== Selection #2(9) ====
[0, 9, 5, 1, 4] 
5 1 4 swap min (1) >  9
[0, 1, 5, 9, 4] 
==== Selection #3(5) ====
[0, 1, 5, 9, 4] 
9 4 swap min (4) >  5
[0, 1, 4, 9, 5] 
==== Selection #4(9) ====
[0, 1, 4, 9, 5] 
5 swap min (5) >  9
[0, 1, 4, 5, 9] 
Selection sort ended
Selection sorted elements
[0, 1, 4, 5, 9]

Time complexity of Selection sort

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.

Let’s understand the advantages and disadvantages of the selection sort algorithm:

Advantages of Selection Sort:

Simple and minimal: Selection sort is easy to understand and implement. It is straightforward and simple and can stand next to bubble sort. No complex logic or intricate data structures involved.
Efficient for Small Datasets: When dealing with small array, like a few hundreds or thousands, selection sort performs efficiently like other two sorting Bubble and Insertion. Its simplicity makes it suitable for small-scale sorting tasks.
Internal Sorting Algorithm: Selection sort operates directly on the input array without requiring additional memory space. It doesn’t need auxiliary data structures like merge sort or quicksort. It is thus called internal or in-place sorting.

Disadvantages of Selection Sort:

Inefficient for Large Datasets: As the size of the dataset grows, selection sort becomes less efficient. Its time complexity is O(n^2) in both the worst and average cases. For large lists, this can lead to slow performance.
Not Optimal for Partially Sorted Data: Selection sort doesn’t take advantage of any existing order in the data. Even if some elements are already in their correct positions, selection sort still performs unnecessary swaps.
Not a Stable Sorting Algorithm: Stability refers to maintaining the relative order of equal elements. Selection sort doesn’t guarantee stability, meaning identical elements may change their order during sorting.

In summary, while selection sort is easy to grasp and works well for small datasets, its inefficiency for larger lists and lack of stability make it less suitable for more complex scenarios123.