# 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, arr, arr….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 &lt;stdio.h&gt;
#include&lt;conio.h&gt;

void selectionSort(int arr[], int size) {
for (int step = 0; step &lt; size - 1; step++) {
int min = step;
int temp;
for (int i = step + 1; i &lt; size; i++) {
if (arr[i] &lt; arr[min])
min = i;
}
temp = arr[min];
arr[min] = arr[step];
arr[step] = temp;
}
}

int main() {
int arr,i,j,n,key;
printf("Enter the number of elements you want to sort:\n");
scanf("%d",&amp;n);
printf("Now enter the %d elements you want to sort: \n",n);
for(i=0;i&lt;n;i++){
scanf("%d",&amp;arr[i]);
}
printf("before sorting:\n");
for(i=0;i&lt;n;i++){
printf("%d \t",arr[i]);
}
selectionSort(arr, n);
printf("\n After Sorting using Selection Sort:\n");
for (int i = 0; i &lt; 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.