Selection Sort | DSA for beginners in Tamil | Mastering Data Structures and Algorithms

Selection sort is a simple sorting algorithm that repeatedly selects the next-smallest element from the unsorted portion of the data and moves it to the sorted portion. It works by dividing the input list into two parts: the sorted portion, which is built up from left to right at the front (left) of the list, and the unsorted portion, which occupies the rest of the list. Initially, the sorted portion is empty and the unsorted portion is the entire input list.

The algorithm proceeds by finding the smallest element in the unsorted portion of the list and swapping it with the leftmost unsorted element (this puts the smallest element in its correct position in the sorted portion of the list). Then, the algorithm advances the boundary between the sorted and unsorted portions of the list one element to the right, and repeats the process of finding the smallest element in the unsorted portion and swapping it with the leftmost unsorted element. This continues until the entire input list is sorted.

Here is an example of selection sort applied to the list [5, 2, 9, 1, 5, 6]:

The unsorted portion is [5, 2, 9, 1, 5, 6], and the sorted portion is empty.
The smallest element in the unsorted portion is 1, so it is swapped with the first unsorted element, 5. The unsorted portion is now [1, 2, 9, 5, 5, 6], and the sorted portion is [5].
The smallest element in the unsorted portion is 2, so it is swapped with the first unsorted element, 1. The unsorted portion is now [2, 9, 5, 5, 6], and the sorted portion is [5, 1].
The smallest element in the unsorted portion is 5, so it is swapped with the first unsorted element, 2. The unsorted portion is now [5, 9, 5, 6], and the sorted portion is [5, 1, 2].
The smallest element in the unsorted portion is 5, so it is swapped with the first unsorted element, 5. The unsorted portion is now [5, 9, 6], and the sorted portion is [5, 1, 2, 5].
The smallest element in the unsorted portion is 6, so it is swapped with the first unsorted element, 5. The unsorted portion is now [9], and the sorted portion is [5, 1, 2, 5, 6].
The smallest element in the unsorted portion is 9, so it is swapped with the first unsorted element, 9. The unsorted portion is now empty, and the sorted portion is [5, 1, 2, 5, 6, 9].

The selection sort algorithm has a time complexity of O(n^2) in the worst and average cases, and a space complexity of O(1) because it sorts the input in place, i.e. it does not require any additional memory.