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]
>Solution :
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)