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

Page Contents

## 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.
First Pass:

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

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

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.

### 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;
}
```

### 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)