349. Selection Sort

What is Selection Sort??

Selection sort is a simple sorting algorithm that builds the sorted array one item at a time. This sorting is efficient for small data sets, not efficient for large data sets. This is in-place sorting algorithm.

How Selection Sort algorithm works??

1. This algorithm divides the given input list into two parts, first part ( built from left to right) which is already sorted and second part which is still not sorted (means rest of the items in the given list)
2. Initially the sorted list is empty and unsorted list is contains all the items (given unsorted list).
3. Algorithm starts with finding the smallest element in unsorted list and swaps it with the leftmost element (first element) in the unsorted list. The smallest element which was swapped is part of sorted list now so increase the starting index of unsorted list for the next iteration.
4. Repeat the step 3 till the entire list is sorted (sorted list have all the element and unsorted list is empty).
5. See the animation below for more understanding.

Time Complexity: O(N²)

Output:

Original Array: [5, 1, 9, 3, 2, 10, 4, 7]
(Selection Sort)- Sorted Array: [1, 2, 3, 4, 5, 7, 9, 10]

Reference: Wiki