CODEWITHSUNDEEP
performancesortingselection
user2188910
user2188910

Reputation: 151

Big(0) running time for selection sort

You are given a list of 100 integers that have been read from a file. If all values are zero, what would be the running time (in terms of O-notation) of a selection sort algorithm.

I thought it was O(n) because selection sort starts with the leftmost number as the sorted side. then it goes through the rest of the array to find the smallest number and swaps it with the the first number in the sorted side. But since they are all zeros then it won't swap any numbers (or so I think).

my teacher said that it is O(n^2). can anyone explain why?

Upvotes: 1

Views: 1941

Answers (1)

dialer
dialer

Reputation: 4844

Selection sort is not adaptive. Each element will always be compared with each other element (Compare n elements with n other elements → n^2 comparisons). Thus, selection sort always has O(n^2) comparisons. It has, however, O(n) swaps.

Think of a table with n rows and n colums, and each cell needs a comparison to fill the value (except the diagonal).

More info on this amazing website

Upvotes: 1

Related Questions