What is the number of swaps required to sort n elements using selection sort, in the worst case?
The site i am referring says theta(n).
Shouldnt it be theta(n2), cuz worst case it requires n swaps for each of the n elements.

7 Years
Discussion Span
Last Post by Narue

How do you figure that?

Worst case, ya, it requires n swaps, if say the array is in the descending order ...

so is the correct answer theta(n) ???


Worst case, ya, it requires n swaps

Not for each element (which is what you stated previously). Selection sort requires at most n-1 swaps total because a swap is only performed after selecting the item to move (or not move, depending on the intermediate relative order). Thus, the worst case for swaps is indeed theta(n).


ok cool, just to summarize,
number of swaps : n-1 or theta(n)
worst case running time : O(n2) ..

narue, correct ???


Yup. O(n2) running time isn't wrong, but you can tighten it to theta(n2) if you want. Best, average, and worst cases for selection sort are (typically) all the same.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.