Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

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]

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

>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)

Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading