Selection sort in Data structure is techniques to sort the elements into a particular order.

Selection sort

What is Selection sort?: The main idea behind the selection sort is to find the minimum or maximum number in the given unsorted array and place that number in its correct position in a sorted array.

Selection sort technique:

In this sorting technique, we compare the first element within number with the second number if it is small then we save these number otherwise not.

Then again the first element is compared with the 3rd element if it is less we swap first element and the third element. Again we test the first element with the fourth element and so on.

This is pass 1 for sorting after this past we will get the smallest number at the top.

In this pass 2, we compare a second element with the third element, if it is less we perform sorting else not. Then the second compare with fourth and so on.

This process continues until we get a sorted list.
Let’s see How selection sort works?

Selection sort example

Consider the following array of 5 number and perform selection sort.
Selection sort in Data StructureFirst Pass:

Selection sortAfter the first pass, we get 10 at its correct position.
Second Pass:

Selection sortAfter the second pass, we get 20 at its correct position.
Third Pass:

Selection sort technique

After the third pass, we get 50 at its correct position.

Fourth Pass:

After the Fourth pass, we get all elements at its correct position.
Sorted array – 10 20 50 60 70
Passes required for sorting this array N-1 = 5-1 = 4. As we have 5 number passes are 4

Selection sort requires passes for n number is n -1.

Selection sort algorithm

  1. Set MIN to location 0
  2. Search MIN value in the list
  3. if found Swap with value at location MIN
  4. Increment MIN to next element
  5. Repeat until the list is sorted.

Flowchart for selection sort

Flowchart for selection sort
Flowchart for selection sort

Selection sort program in c

#include <stdio.h>
int main()
{
int array[100], n, c, d, MIN, swap;
printf("Enter number of elements\n");
scanf("%d", &n); //Enter range of array
printf("Enter %d integers\n", n);
for ( c = 0 ; c < n ; c++ )
scanf("%d", &array[c]); // Enter values in array
for ( c = 0 ; c < ( n - 1 ) ; c++ ) //code for selection sort
{
MIN = c;
for ( d = c + 1 ; d < n ; d++ )
{
if ( array[MIN] > array[d] )
MIN = d;
}
if ( MIN != c )
{
swap = array[c];
array[c] = array[MIN];
array[MIN] = swap;
}}
printf("Sorted list in ascending order:\n");
for ( c = 0 ; c < n ; c++ )
printf("%d\n", array[c]);
return 0;
}
Output:

Selection sort

The complexity of selection sort

The worst-case and average-case complexity: O(n2)
The Best case complexity of selection sort: O(n2)
Space complexity for selection sort: O(1)

Advantages of selection sort

  • It works very well with a small number of an array(with minimum data).
  • Selection sort doesn’t require any additional space while implementing.

Disadvantages of selection sort

  • Not as efficient while working with a large set of data.
  • It requires n2 passes of an n element

Write A Comment