Selection Sort is a simple comparison-based sorting algorithm. It divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list.

Initially, the sorted sublist is empty, and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

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

### 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) {`

This function sorts 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() {`

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

**Iterate through each element of the array except the last one.**Each iteration of`step`

marks where the next smallest unsorted element will go.**Find the smallest element**in the rest of the array (i.e., from`arr[step+1]`

to`arr[size-1]`

).**Swap**the smallest element found with the element at the current`step`

index.**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

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