Editing Selection sort (section)

== Variants ==

[[Heapsort]] has been described as "nothing but an implementation of selection sort using the right [[data structure]]."<ref>{{cite book |first=Steven |last=Skiena |author-link=Steven Skiena |title=The Algorithm Design Manual |edition=3rd |publisher=Springer |year=2008 |page=116 |chapter=Searching and Sorting |isbn=978-3-030-54255-9 |quote=The name typically given to this algorithm, ''heapsort'', obscures the fact that the algorithm is nothing but an implementation of selection sort using the right data structure. |doi=10.1007/978-3-030-54256-6_4}}<!--DOI for chapter--></ref> It greatly improves the basic algorithm by using an [[implicit data structure|implicit]] [[heap (data structure)|heap]] data structure to find and remove each lowest element in <math>\Theta(\log n)</math> time, instead of normal selection sort's <math>\Theta(n)</math> inner loop, reducing the total running time to <math>\Theta(n\log n)</math>.

A bidirectional variant of selection sort (called '''double selection sort''' or sometimes '''cocktail sort''' due to its similarity to [[cocktail shaker sort]]) finds ''both'' the minimum and maximum values in the list in every pass. This requires three comparisons per two items (a pair of elements is compared, then the greater is compared to the maximum and the lesser is compared to the minimum) rather than regular selection sort's one comparison per item, but requires only half as many passes, a net 25% savings.

Selection sort can be implemented as a [[Sorting algorithm#Classification|stable sort]] if, rather than swapping in step 2, the minimum value is ''inserted'' into the first position and the intervening values shifted up. However, this modification either requires a data structure that supports efficient insertions or deletions, such as a linked list, or it leads to performing <math>\Theta(n^{2})</math> writes.

In the '''bingo sort''' variant, items are sorted by repeatedly looking through the remaining items to find the greatest value and moving ''all'' items with that value to their final location.<ref>{{DADS|Bingo sort|bingosort}}</ref> Like [[counting sort]], this is an efficient variant if there are many duplicate values: selection sort does one pass through the remaining items for each ''item'' moved, while Bingo sort does one pass for each ''value''.  After an initial pass to find the greatest value, subsequent passes move every item with that value to its final location while finding the next value as in the following [[pseudocode]] (arrays are zero-based and the for-loop includes both the top and bottom limits, as in [[Pascal (programming language)|Pascal]]):

<syntaxhighlight lang="pascal">
bingo(array A)

{ This procedure sorts in ascending order by
  repeatedly moving maximal items to the end. }
begin
    last := length(A) - 1;

    { The first iteration is written to look very similar to
      the subsequent ones, but without swaps. }
    nextMax := A[last];
    for i := last - 1 downto 0 do
        if A[i] > nextMax then
            nextMax := A[i];
    while (last > 0) and (A[last] = nextMax) do
        last := last - 1;

    while last > 0 do begin
        { Each main loop searches for the new nextMax while
          swapping items equal to prevMax into place. }
        prevMax := nextMax;
        nextMax := A[last];
        for i := last - 1 downto 0 do
             if A[i] > nextMax then
                 if A[i] <> prevMax then
                     nextMax := A[i];
                 else begin
                     swap(A[i], A[last]);
                     last := last - 1;
                 end
        while (last > 0) and (A[last] = nextMax) do
            last := last - 1;
    end;
end;
</syntaxhighlight>

Thus, if on average there are more than two items with the same value, bingo sort can be expected to be faster because it executes the inner loop fewer times than selection sort.
<!--

If you came here to write an implementation of selection sort, note that this page used to have implementations but they were moved to Wikibooks. Therefore, implementations should not be added here.

-->