Insertion sort in Python

Question

I have a homework assignment in Python and ran into a brain freeze. So i'm supposed to do O(nˇ2) exercise using insertion sort. For example i have a two lists [] and [5,8,1,1] and the program should insert values from one list to another by removing from first and in correct order into another: [][5,8,1,1] = [5][8,1,1] = [5,8][1,1] = [1,5,8][1] = [1,1,5,8][]

I've came up with something, don't know if i'm on right track but this seems the most reasonable. Indents are in order but copying code here somehow messed it up. P.S sorry for Estonian language, it's compulsory to write code in Estonian.

def pisteMeetod2(t2ishulk):
    tulemus = [] #new list
    hulgacopy = t2ishulk[0:len(t2ishulk)] #main list
    for el in t2ishulk: #going through first list
        if not tulemus: #if list empty (which it at the beginning is) then from here
            tulemus.append(el)
            del hulgacopy[0]
        else:
            for elemendid in tulemus: #check if there is a lower element from new list
                n = 0
                if hulgacopy[0] <= tulemus[n]:
                    tulemus.insert(n-1,el)
                    del hulgacopy[0]
                    break
                n = n + 1

So right now i'm in trouble what do to with second loop. After it has finished checking for elements in result list called "tulemus" and if it does not find any matches how should i continue my code so it would append the "el" into tulemus.

amgaera · Accepted Answer · 2014-09-13 15:39:01Z

3

You can add an else clause to the inner for loop:

for elemendid in tulemus: #check if there is a lower element from new list
    n = 0
    if hulgacopy[0] <= tulemus[n]:
        tulemus.insert(n, el)
        del hulgacopy[0]
        break
    n = n + 1
else:
    tulemus.append(el)
    del hulgacopy[0]

Its body gets executed if the loop wasn't terminated using break. You can read more about else clauses on loops in Python's official tutorial.

Please also note that if you find an insertion point while iterating, you should use tulemus.insert(n, el) instead of tulemus.insert(n-1, el) to insert the current element there. Otherwise you'll end up inserting at the end of the list (index -1) when n == 0.

edited Sep 13, 2014 at 15:39

answered Sep 13, 2014 at 15:30

amgaera

1,8381 gold badge15 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Insertion sort in Python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related