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
Junior Poster in Training
Recommended Answers
Jump to Postcuz worst case it requires n swaps for each of the n elements
How do you figure that?
Jump to PostWorst 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 …
All 5 Replies
Narue
5,707
Bad Cop
Team Colleague
cuz worst case it requires n swaps for each of the n elements
How do you figure that?
tubby123
-4
Junior Poster in Training
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) ???
Narue
5,707
Bad Cop
Team Colleague
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).
tubby123
-4
Junior Poster in Training
ok cool, just to summarize,
number of swaps : n-1 or theta(n)
worst case running time : O(n2) ..
narue, correct ???
Narue
5,707
Bad Cop
Team Colleague
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.
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.