Source

Sort this messy list / insertion.py

Full commit




class Insertion(object):
    """
    Insertion sort - O(n^2)
    """
    def __init__(self, l):
        self.unsorted_list = l

    def sort(self):
        l = self.unsorted_list
        for i in range(len(l)):
            m=l[i]
            for j in range(i+1):
                if m<l[j]:
                    for k in reversed(range(j+1,i+1)):
                        l[k]=l[k-1]
                    l[j]=m
                    break

class Insertion_Better(object):
    """
    Insertion sort - O(n^2)
    """
    def __init__(self, l):
        self.unsorted_list = l

    def sort(self):
        l = self.unsorted_list
        for i in range(len(l)):
            m=l[i]
            for j in range(i+1):
                if m<l[j]:
                    l[j+1:i+1] = l[j:i]
                    l[j]=m
                    break