Getting the time complexity of a selection sort-CodePudding

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]

CodePudding user response：

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

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.

CodePudding user response：

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)