Selection Sort - Eishaaya/GMRDataStructuresTest GitHub Wiki

Sorting by selecting

Selection sort is similar to bubble sort in that every element is compared to every other element, and the region that is already sorted is not touched. The main difference here is that the swapping is not done until the index of the smallest value is found in the subarray that is being sorted. Once the index is found, the value at that index is swapped with the current value. Essentially, you must search the unsorted part of the array for the next smallest item and swap with the current index of the sorted.

Notice that selection sort performs significantly fewer operations than bubble sort, only swapping when the proper index is found.

Selection sort, compared to bubble sort, minimizes the amount of swaps. Values are swapped only when necessary. Therefore, selection sort might be used when swapping is a costly operation.

Selection sort is not an adaptive sort. Even if the array is partially sorted, each element is still compared to find the smallest value, there is no exiting the loop early.

Selection sort is not a stable sort. Selection sort works by finding the minimum element and then inserting the element into its correct position by swapping with the element which is in the position of its minimum element.

Try and Implement this sort on your own! Look at the link in the footer for a visualizer if you need it (also to make sure your solution is actually a selection sort)

References

<-- Previous | Next -->