Home Arrays Selection Sort

Selection Sort

by nikoo28
0 comment

As the name suggests SELECTION SORT involves selecting an element. Now the question arises, as to how should we select this element. What is the criteria? Where should we put it? All these answers are given in the algorithm for SELECTION SORT.

In selection sort, what we do is:-

  1. Start from the first position in the array.
  2. Traverse the remaining array to find the smallest number
  3. Swap this smallest number with the number we selected in the first place.
  4. Repeat steps 2 and 3 with the next position.

Let us try to understand this algorithm with the help of this diagram.

Selection Sort illustration
Fig: Selection Sort

As we can see we have an unsorted array in the first step. The red blocks represent sorted elements and the blue elements represent the sorted ones.

  • We start with the element 7 and then scan the remaining array for the minimum element.
  • 1 is the minimum element and thus we swap 1 and 7.
  • Now we start with the second element that is 4, and scan the remaining array for the minimum element.
  • 2 is the minimum element and thus we swap 2 and 4.
  • Similarly we swap 5 and 4
  • This process continues and finally our complete array is sorted.

Here is an implementation of the above algorithm.

Code:

#include<stdio.h> // function to swap two integers void swap(int *x, int *y) { int temp = *x; *x = *y; *y = temp; } //defining a function to perform selection sort on array arr[] of given size void selectionSort(int arr[], int size) { int i,j; for(i = 0; i < size; i++) { //a variable to store the position with minimum element int min_pos = i; //we need to check the remaining elements for(j = i + 1; j < size; j++) { //compare each element and get the minimum element's position if(arr[j] < arr[min_pos]) { min_pos = j; } } //now 'min_pos' contains the position with minimum element //so we swap the elements swap(&arr[i], &arr[min_pos]); } } // driver function to test the above function int main(void) { int i; int arr[10] = {3, 4, 7, 1, 10, 8, 2, 22, 99, 50}; selectionSort(arr,10); printf("SORTED array:- "); for(i = 0; i < 10; i++) printf("%d ",arr[i]); return 0; }
Time Complexity: O(n^2)
Space Complexity: O(1)

The run-time of this algorithm is always O(n2) in any case. But upon analysis we can also say that this algorithm always performs swaps in the order of O(n).

Thus this type of algorithm can be helpful when we need to sort few number of elements and the cost of swapping elements is very high.

Video Explanation:

0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More