selection sort in data structure is techniques to sort the elements into a particular order.
In this tutorial we will learn new sorting technic Selection Sort.
Selection sort logic
Selection sort algorithm
1. In this technique we compare first element within number with second number if it is small then we save these number otherwise not.
2. Then again first element is compared with the 3rd element if it is less we swap first element and third element.
3. Again we test first element with the fourth element and so on.
4. This is pass 1 for sorting after this past we will get a smallest number at the top.
5. In this pass 2, we compare a second element with the third element, if it is less we perform sorting else not. Then second compare with fourth and so on.
6. This process continues till we get sorted list.
Selection sort require passes for n number is n -1.
Time complexity of selection sort for worst case O(n).
lets see step by step sorting using selection sort
Selection sort example
Consider following array of 5 number and perform selection sort.
First Pass :-
Second Pass :-
Third Pass :-
Pass 4:-
Output of example
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
Advantages of selection sort
- It works very simple with small number of array(with minimum data).
- selection sort don’t required any additional space while implementing.
Disadvantages of selection sort
- Not as efficient while working with large set of data.
- It requires n2 passes of n element.
Program for selection sort in data structure
| 123456789101112131415161718192021222324252627282930313233343536 | #include <stdio.h>int main(){int array[100], n, c, d, position, swap;printf(“Enter number of elements\n”);scanf(“%d”, &n); //Enter range of arrayprintf(“Enter %d integers\n”, n);for ( c = 0 ; c < n ; c++ )scanf(“%d”, &array[c]); // Enter values in arrayfor ( c = 0 ; c < ( n – 1 ) ; c++ ) //code for selection sort{position = c;for ( d = c + 1 ; d < n ; d++ ){if ( array[position] > array[d] )position = d;}if ( position != c ){swap = array[c];array[c] = array[position];array[position] = swap;}}printf(“Sorted list in ascending order:\n”);for ( c = 0 ; c < n ; c++ )printf(“%d\n”, array[c]);return 0;} |
Output of program:
Explanation :
1. Take number from user.
=> n = 5
2. Take n numbers from user.
=> array[]= 10,4,78,4,9
3. Traverse the array from start to end.
Using selection sort logic sort array
4. Print sorted array.