Selection sort: Difference between revisions

Revision as of 12:31, 25 January 2023

Revision as of 12:34, 25 January 2023

Line 131:

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.