➤Selection sort is a sorting algorithm that repeatedly selects the smallest element from an unsorted array and swaps it with the element in the first position. It then iterates through the remaining unsorted subarray until the entire array is sorted. The algorithm has a time complexity of O(n^2).
How Insertion-sort works?
1. Selection sort starts by dividing the input array into two parts: the sorted subarray and the unsorted subarray.
2.Initially, the sorted subarray is empty, while the unsorted subarray contains all the elements of the input array.
3.The algorithm then finds the minimum element in the unsorted subarray and swaps it with the first element of the unsorted subarray, thereby adding the minimum element to the sorted subarray.
4.The algorithm repeats this process on the remaining unsorted subarray until the entire array is sorted.
5.At each iteration, the sorted subarray grows by one element, and the unsorted subarray shrinks by one element.
6.The algorithm has a time complexity of O(n^2) because it needs to compare each element in the unsorted subarray to find the minimum element
How the element compare?
Demonstration of Selection Sort
Optimized Selection Sort
➤Optimized selection sort is a variation of the selection sort algorithm that improves its performance by reducing the number of swaps required to sort the input
array. In the standard selection sort algorithm, at each iteration, the minimum element is swapped with the first element of the unsorted subarray, even if it is already in its
correct position in the sorted subarray. Optimized selection sort avoids these unnecessary swaps by only swapping the minimum element if it is not already in its correct position.
