Editing Selection sort (section)

== Comparison to other sorting algorithms ==

Among quadratic sorting algorithms (sorting algorithms with a simple average-case of [[Big O notation#Family of Bachmann–Landau notations|Θ(''n''<sup>2</sup>)]]), selection sort almost always outperforms [[bubble sort]] and [[gnome sort]]. [[Insertion sort]] is very similar in that after the ''k''th iteration, the first <math>k</math> elements in the array are in sorted order. Insertion sort's advantage is that it only scans as many elements as it needs in order to place the <math>k+1</math>st element, while selection sort must scan all remaining elements to find the <math>k+1</math>st element.

Simple calculation shows that insertion sort will therefore usually perform about half as many comparisons as selection sort, although it can perform just as many or far fewer depending on the order the array was in prior to sorting. It can be seen as an advantage for some [[real-time computing|real-time]] applications that selection sort will perform identically regardless of the order of the array, while insertion sort's running time can vary considerably. However, this is more often an advantage for insertion sort in that it runs much more efficiently if the array is already sorted or "close to sorted."

While selection sort is preferable to insertion sort in terms of number of writes (<math>n-1</math> swaps versus up to <math>n(n-1)/2</math> swaps, with each swap being two writes), this is roughly twice the theoretical minimum achieved by [[cycle sort]], which performs at most ''n'' writes.  This can be important if writes are significantly more expensive than reads, such as with [[EEPROM]] or [[Flash memory]], where every write lessens the lifespan of the memory.

Selection sort can be implemented without unpredictable branches for the benefit of CPU [[branch predictor]]s, by finding the location of the minimum with branch-free code and then performing the swap unconditionally.

Finally, selection sort is greatly outperformed on larger arrays by <math>\Theta(n\log n)</math> [[divide and conquer algorithm|divide-and-conquer algorithms]] such as [[mergesort]]. However, insertion sort or selection sort are both typically faster for small arrays (i.e. fewer than 10–20 elements). A useful optimization in practice for the recursive algorithms is to switch to insertion sort or selection sort for "small enough" sublists.