CODEWITHSUNDEEP
algorithmselection-sort
PythonnLearner
PythonnLearner

Reputation: 57

Getting the time complexity of a selection sort

I created a code for selection sort, but my teacher asked me what the time complexity of my code is, so I need help to get it. I'm not sure if my code is the same with the other selection sort with a worst time case of O(n^2) and a best time case of O(n).

code:

def selection(collection):
for endnum in range(len(collection)-1, 0, -1):
    print(collection)
    max_idx = endnum
    if max(collection[0:endnum]) > collection[endnum]:
        max_idx = collection.index(max(collection[0:endnum]))
    collection[endnum], collection[max_idx] = collection[max_idx], collection[endnum]

Upvotes: 0

Views: 627

Answers (2)

rici
rici

Reputation: 241881

Selection sort doesn't have a best case. It's always O(n²), because each step needs to find the largest (or smallest) element in the unsorted portion of the array, which requires scanning the entire unsorted segment.

Your version is not different except that you rather unnecessarily compute the maximum twice and then do a third scan to find its index. However, doing three times as much work as is necessary is "just" a constant factor, so the asymptotic complexity doesn't change. The cycles you waste are real, though.

Upvotes: 4

MBo
MBo

Reputation: 80287

Your code hase the same complexity O(n^2) as usual selection sort, you just fill sorted items from the end rather than from start.

There are n-1 loops with run lengths n,n-1, n-2..1, so sum of arithmetic progression gives about n*(n-1)/2 comparisons and n exchanges.

Also note that the best time case of selection sort is quadratic, not linear (selection sort doesn't retrieve information to stop early)

Upvotes: 2

Related Questions