To The Left, To The Left
Sorting Algorithms: Selection Sort — JavaScript
In computer science, selection sort is an in-place comparison sorting algorithm. It has an O(n2) time complexity, which makes it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity and has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.
One thing which distinguishes selection sort from other sorting algorithms is that it makes the minimum possible number of swaps, n − 1 in the worst case. (Wikipedia)
Selection Sort improves on the bubble sort by making only one exchange for every pass through the list. Selection Sort divides the array into 2 subsections: the sorted elements (at the front) and the remaining unsorted elements. This pattern sorts an array by repeatedly finding the minimum element in the unsorted subsection and placing it at the end of the sorted subsection.
With each pass, it finds the smallest element in the unsorted subsection and swaps it with the leftmost element in the unsorted subsection. Since the swap adds an element to the end of the sorted subsection and removes an element from the unsorted subsection, the sorted subsection grows by 1 and the unsorted subsection shrinks by 1 with each pass.
Given an array of N items and L = 0, Selection Sort will:
- Find the position X of the smallest item in the range of [L…N−1],
- Swap X-th item with the L-th item,
- Increase the lower-bound L by 1 and repeat Step 1 until L = N-2.
Look Left
JavaScript Example
📚 Resources 👀
Udemy — JavaScript Algorithms and Data Structures Masterclass
Data Structure and Algorithms Selection Sort
