Selection Sort Algorithm and Program in C

Selection sort is a sorting algorithm that has an O(n2) time complexity for all the cases like best, average, and worst case.

How selection sort works

Suppose we have an array Arr of length n, where n is 0…..n and elements are arr[0], arr[1], arr[2]….arr[n]
In the Selection sort technique to sort an array arr, first find the minimum element of the array.
After finding the minimum in the array exchange it with the first element.
So in the first pass, we have a minimum element of an array at the first position.
Similarly in the second pass, the second minimum will be at the second position of the array.
The same procedure will be followed by the rest of the element of the array.
In each pass, one element will be sorted.
Selection sort performs worse than insertion sort because in best case time complexity of insertion sort is O(n) but for selection sort, best case time complexity is O(n^2).

How selection sort works with example

Here we will sort the below array using selection sort.

After First Pass

In first pass at position 1 index 0, array element 1 is sorted.

After Second Pass

In Second pass at position 2 index 1, array element 2 is sorted.

After Third Pass

In the third pass at position 3 index 2, array element 3 is sorted.

After Fourth Pass

In the Fourth pass at position 4 index 3, array element 4 is sorted. And as well as our array become sorted

Selection Sort Algorithm

Step 1 − Set the first element of array means 0 location element as MIN
Step 2 − Find the minimum element in the array
Step 3 − If minimum found then swap it with the value of location MIN
Step 4 − Increase MIN by 1 to point to the next element of the array
Step 5 − Repeat until the list is sorted

Psuedo Code of Selection Sort

SMALLEST (ARR, K, N, POS)
Step 1: [INITIALIZE] SET MIN = ARR[K]
Step 2: [INITIALIZE] SET POS=K
Step 3: Repeat for J= K+1 to N
         IF MIN > ARR[J]
          SET MIN = ARR[J]
          SET POS=J
        [END OF IF]
       [END OF LOOP]
Step 4: RETURN POS

C Program for selection sort

#include <stdio.h>
#include<conio.h>
 
void selectionSort(int arr[], int size) {
  for (int step = 0; step < size - 1; step++) {
    int min = step;
    int temp;
    for (int i = step + 1; i < size; i++) {
      if (arr[i] < arr[min])
        min = i;
    }
    temp = arr[min];
    arr[min] = arr[step];
    arr[step] = temp;
  }
}
 
int main() {
  int arr[100],i,j,n,key;
  printf("Enter the number of elements you want to sort:\n");
  scanf("%d",&n);
  printf("Now enter the %d elements you want to sort: \n",n);
  for(i=0;i<n;i++){
    scanf("%d",&arr[i]);
  }
  printf("before sorting:\n");
  for(i=0;i<n;i++){
    printf("%d \t",arr[i]);
  }
  selectionSort(arr, n);
  printf("\n After Sorting using Selection Sort:\n");
  for (int i = 0; i < n; ++i) {
    printf("%d \t", arr[i]);
  }
  printf("\n");
  getch();
}

Output:

Enter the number of elements you want to sort:
6
Now enter the 6 elements you want to sort: 
23
11
12
54
2
11
before sorting:
23      11      12      54      2       11 
 After Sorting using Selection Sort:
2       11      11      12      23      54

Time Complexity of Selection Sort

Best Case Complexity: O(n2)
In selection best-case scenario is when an array is already sorted in ascending order.

Average Case Complexity: O(n2)
In selection Average case scenario is when an array is in jumbled order means neither ascending nor descending.

Worst Case Complexity: O(n2)
In selection worst-case scenario is when an array is in descending order and we want to sort it in ascending order.

Space Complexity of Selection Sort

Space complexity is O(1) because an extra variable temp is used.

Advantages of Selection Sort

Selection Sort is easy to implement.
It can be used for small data sets.
It is more efficient than bubble sort because swaps are O(n) as compared to O(n2) of bubble sort

[wpusb]