Straight Selection Sorting

Selection sorting refers to a class of algorithms for sorting a list of items using comparisons. These algorithms select successively smaller or larger items from the list and add them to the output sequence. Straight selection is an O(n2) member of the class in which we repeatedly scan the remaining unsorted items in the list in linear time, find the largest (or smallest), and add it to the result. Since it looks at all unprocessed data on each pass, it performs no better for nearly sorted inputs than for random or reverse-sorted inputs, unlike insertion sort.

The version in this demonstration makes N-1 passes, finding the index of the largest unsorted element each time, and then swapping the largest unsorted item with the last unsorted item—thus moving the largest remaining element into position on each pass. On each pass, the elements that have been searched for the maximum are shown in green, with the maximum element indicated by a "V" above. As-yet unexamined and unsorted elements are shown in pink.

Fast Slow
Input size:
Initial array: Array: Inversion count: # comparisons: