# Selection Sort in C

## What is Selection Sort in C

In this Sorting technique the list is divided into two parts. first one is left end and second one is right end .  The selection Sort is very  simple sorting algorithm.

 Time Complexity (Best) Ω(n2) Time Complexity (Avg) Θ(n2) Time Complexity (Worst) O(n2) Space Complexity O(1)

## Steps for Selection Sort in C

There are following Step of selection sort algorithm.

• Step 1-Select the smallest value in the list.
• Step 2-Swap smallest value with the first element of the list.
• Step 3-Again select the smallest value in the list (exclude first value).
• Step 4- Repeat above step for (n-1) elements untill the list is sorted.

### Implementation of Selection Sort

• We have been given a unsorted array. which we’ll  make  a sorted array using selection sort. first of all  find the smallest value in the array and then swap smallest value with the starting value.
• According to the below image,  8 is smallest value in this array so 8 is swapped with the first element that is 72.
• Similarly, in the next iteration we’ll  find the next smallest value, excluding the starting value so in this array  10 is second smallest value, which is to be swapped with 50.
• These iteration will continue until we have the largest element to the right most end, along with all the other elements in their correct position.
• And then we can finally say that the given array is converted in sorted array.

### Code of Selection sort in C

#### Output

`Before sorting: 72 50 10 44 8 20After sorting: 8 10 20 44 50 72`

## Performance

The Selection Sort best and worst case scenarios both follow the time complexity format O(n^2) as the sorting operation involves two nested loops. The size of the array again affects the performance.[1]

#### Strengths

• The arrangement of elements does not affect its performance.
• Uses fewer operations, so where data movement is costly it is more economical

#### Weaknesses

• The comparisons within unsorted arrays requires O(n^2) which is ideal where n is small

Ω(n2)

Θ(n2)

O(n2)

## Space Complexity

O(1)

### Quiz Time

Question 1. Array = [10, 11, 12, 13, 14, 15], the number of iterations bubble sort(without flag variable) and Selection sort would take –

1. 5 and 5
2. 5 and 4
3. 4 and 4
4. 6 and 6

(Cognizant – Mettl Test)

In bubble sort they are talking about passes, even though the question says iterations.

A bubble sort with n items takes (n-1) passes.

In selection sort also for n items its (n-1) passes.

Thus, 4 and 4 is answer

Option C

Question 2. Array = [10, 11, 12, 13, 14, 15], the number of iterations bubble sort(with flag variable) and Selection sort would take –

1. 5 and 5
2. 5 and 4
3. 4 and 4
4. 1 and 4

(Cognizant – Mettl Test)

In bubble sort they are talking about passes, even though the question says iterations.

A bubble sort with n items takes (n-1) passes. But, since the whole array is sorted, bubble sort will have just one pass to realize the array is sorted and abandon other passes

In selection sort also for n items its (n-1) passes, even though the array is sorted

Thus, 1 and 4 is answer

Option C

Question 3. What is the best case complexity of selection sort?

1. O(nlogn)
2. O(logn)
3. O(n)
4. O(n2)

(Wipro – AMCAT Test)

In selection sort all cases the time complexity is : O(N^2)

Explanation: The best, average and worst case complexities of selection sort is O(n2).
(n-1) + (n-2) + (n-3) + …. + 1 = (n(n-1))/2 ~ (n2)/2.

Question 4. Array[] = {72, 50, 10, 44, 8, 20} how would the array look like in iteration 4

1. 8, 10, 44, 20, 72, 50
2. 8, 10, 20, 44, 72, 50
3. 8, 10, 20, 44, 50, 72
4. None

(Wipro – AMCAT Test)