Selection Sort: Algorithm, Program in C

Selection Sort is a simple way to sort numbers. It divides the list into two parts: a sorted part at the start and an unsorted part for the rest. At first, the sorted part is empty. The algorithm finds the smallest number in the unsorted part, swaps it with the first number of the unsorted part, and then moves the sorted boundary one step right. This is repeated until the whole list is sorted. Selection Sort is slow because it always takes about n² steps, no matter how the list looks.

How selection Sort works

• Suppose we have an array Arr of length n, where n is 0…..n-1 and elements are arr[0], arr[1], arr[2]….arr[n-1]
• 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²).

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 the array (index 0) as the current minimum (MIN).
Step 2 −Find the minimum element in the unsorted part of the array.
Step 3 − Swap this minimum element with the element at the MIN position.
Step 4 − Move MIN to the next position (MIN = MIN + 1).
Step 5 −Repeat steps 2–4 until the entire array 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 

Explanation of Selection sort program

This C program implements the Selection Sort algorithm to sort an array of integers in ascending order. Here’s a step-by-step explanation of how this program works:

Including Header Files

#include<stdio.h>
#include<conio.h>

• stdio.h is included for input/output operations (printf, scanf).
• conio.h is included for console input/output operations, like getch() which waits for a character input to pause the program’s termination, allowing users to see the output before the console window closes.

Selection Sort Function

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

The function Selectionsort has the given array arr of size size using the selection sort algorithm.

• It iterates through the array with step indicating the current position being filled with the correct value.
• For each position, it finds the index of the smallest value (min) in the unsorted part of the array (from step + 1 to size - 1).
• It then swaps the smallest found value with the value at the current position step.

The Main Function

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();
}

The main function is the entry point of the program.

• It asks the user for the number of elements they want to sort (n) and reads them into an array arr.
• It prints the array before sorting to show the original order.
• It calls selectionSort(arr, n) to sort the array.
• After sorting, it prints the sorted array.
• Finally, getch() is called to wait for a keystroke before closing, allowing the user to see the sorted array.

How Selection Sort Works in This Program

1. Iterate through each element of the array except the last one. Each iteration of step marks where the next smallest unsorted element will go.
2. Find the smallest element in the rest of the array (i.e., from arr[step+1] to arr[size-1]).
3. Swap the smallest element found with the element at the current step index.
4. Repeat this process until the array is sorted.

Input/Output Process

• The user is prompted to enter the number of elements (n) and then the elements themselves.
• The program displays the array before and after applying the selection sort algorithm.

Time Complexity of Selection Sort

Space Complexity of Selection Sort

Space complexity is O(1) for all the cases.

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(n²) of bubble sort

Disadvantages of Selection Sort

• It is slow for large data because it always takes O(n²) time.
• It does a lot of comparisons, even if the array is already sorted.
• It is not stable, meaning it may change the order of equal elements.
• It is not adaptive, so it does not get faster if the data is partially sorted.
• It is usually slower than Insertion Sort for small data sets.

Conclusion

Selection sort is a simple sorting method that works by repeatedly finding the smallest element from the unsorted part and putting it in the correct position. It is easy to understand and implement, but it is not very efficient for large datasets because it always takes more time compared to better algorithms like Quick Sort or Merge Sort. It is mainly used for learning purposes and small problems.