In [17]:

    

class AbstractQuickSort(object):
    def run(self):
        f = open("QuickSort.txt", "r")
        source = [int(line) for line in f]
        f.close()
        print self.partition(source, 0, len(source)-1)

    def partition(self, A, l, r):
        if l >= r:
            return 0
        self.choose_pivot(A, l, r)
        p = A[l]
        i = l + 1
        for j in xrange(l+1, r+1):
            if A[j] < p:
                A[i], A[j] = A[j], A[i]
                i += 1
        q = i-1
        A[l], A[q] = A[q], A[l]
        return (r-l) + self.partition(A, l, q-1) + self.partition(A, q+1, r)

    def choose_pivot(self, A, l, r):
        raise NotImplementedError()


    

In [18]:

    

class Question1(AbstractQuickSort):
    def choose_pivot(self, A, l, r):
        pass

Question1().run()


    

    




162085

In [19]:

    

class Question2(AbstractQuickSort):
    def choose_pivot(self, A, l, r):
        A[l], A[r] = A[r], A[l]

Question2().run()


    

    




164123

In [20]:

    

class Question3(AbstractQuickSort):
    def choose_pivot(self, A, l, r):
        mid = (l+r)//2
        if A[l] < A[mid] < A[r] or A[r] < A[mid] < A[l]:
            A[l], A[mid] = A[mid], A[l]
        elif A[l] < A[r] < A[mid] or A[mid] < A[r] < A[l]:
            A[l], A[r] = A[r], A[l]

Question3().run()


    

    




138382

In [ ]: