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.
tubby123 -4
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.
cuz worst case it requires n swaps for each of the n elements
How do you figure that?
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.