**Selection Sort-**

- Selection sort is one of the easiest approaches to sorting.
- It is inspired from the way in which we sort things out in day to day life.
- It is an in-place sorting algorithm i.e. it uses no auxiliary data structures while sorting.

**How Selection Sort Works?**

Consider the following elements are to be sorted in ascending order-

6, 2, 11, 7, 5

Selection sort works as-

- It finds the first smallest element (2).
- It swaps it with the first element of the unordered list.
- It finds the second smallest element (5).
- It swaps it with the second element of the unordered list.
- Similarly, it continues to sort the given elements.

As a result, sorted elements in ascending order are-

2, 5, 6, 7, 11

**Selection Sort Algorithm-**

Let A be an array with n elements. The selection sort algorithm used for sorting is as follows-

for (i = 0 ; i < n-1 ; i++) { index = i; for(j = i+1 ; j < n ; j++) { if(A[j] < A[index]) index = j; } temp = A[i]; A[i] = A[index]; A[index] = temp; }

Here,

- i = variable to traverse the array A
- index = variable to store the index of minimum element
- j = variable to traverse the unsorted sub-array
- temp = temporary variable used for swapping

**Selection Sort Example-**

Consider the following elements are to be sorted in ascending order-

6, 2, 11, 7, 5

The above selection sort algorithm works as illustrated below-

**Step-01: For i = 0**

**Step-02: For i = 1**

**Step-03: For i = 2**

**Step-04: For i = 3**

**Step-05: For i = 4**

Loop gets terminated as ‘i’ becomes 4.

The state of array after the loops are finished is as shown-

With each loop cycle,

- The minimum element in unsorted sub-array is selected.
- And placed at the correct location in the sorted sub-array until array A is completely sorted.

**Selection Sort Time Complexity-**

- Selection sort algorithm consists of two nested loops.
- Owing to the two nested loops, it has O(n
^{2}) time complexity.

Time Complexity | |

Best Case | n^{2} |

Average Case | n^{2} |

Worst Case | n^{2} |

**Selection Sort Space Complexity-**

- Selection sort is an in-place algorithm.
- It performs all computation in the original array and no other array is used.
- Hence, the space complexity works out to be O(1).

**Important Notes-**

- Selection sort is not a very efficient algorithm when data sets are large.
- This is indicated by the average and worst case complexities.
- Selection sort uses minimum number of swap operations O(n) among all the sorting algorithms.

To gain better understanding about Selection Sort Algorithm,

Get more notes and other study material of **Design and Analysis of Algorithms (DAA)**.

Watch video lectures by visiting our YouTube channel **LearnVidFun**.