Explain the technique of Selection Sort with an example.

Selection Sort divides the array into two parts — sorted sub-array and unsorted sub-array. In each pass, it finds the minimum element of the unsorted sub-array and swaps it with the leftmost unsorted element moving the sorted sub-array one element to the right.

For example, consider the following unsorted array:

Pass 1

At the start, the smallest element of the array is selected (which is 2) and swapped with the element at 0^th index (which is 9):

At the end of the first pass, the smallest element is in its correct position. Length of sorted sub-array is 1 and unsorted sub-array is 3.

Pass 2

The smallest element of the unsorted sub-array is selected (which is 3) and swapped with the element at 1^st index (which is 5):

At the end of the second pass, length of sorted sub-array is 2 and unsorted sub-array is 2.

Pass 3

The smallest element of the unsorted sub-array is selected (which is 5) and swapped with the element at 2^nd index (which is 9):

With this, the third and final pass ends and the elements of the array are in sorted order.