Page Contents

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**:

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

Share On :