Search code examples
algorithmsortingtime-complexitybig-oselection-sort

Why is Selection Sort said to have O(n) swaps?


I am reading about use cases of Selection Sort, and this source says:

(selection sort is used when...) cost of writing to a memory matters like in flash memory (number of writes/swaps is O(n) as compared to O(n2) of bubble sort)

We can even see O(n^2) swaps in this example: [1, 2, 3, 4, 5]. It's going to have 4 swaps, then 3, then 2, and 1. That is O(n^2), not O(n) swaps. Why do they say the opposite?


Solution

  • A selection sort has a time complexity of O(n2), but only O(n) swaps.

    In each iteration i, you go over all the remaining items (in indexes i and onwards), find the right value to populate that index, and swap it there. So in total you perform O(n2) comparisons, but only O(n) swaps.