#!/usr/bin/python

# Autogenerated with DRAKON Editor 1.5

def quick_sort_demo():
        #item 181
    unsorted = [ "the", "sooner", "we", "start", "this", "the", "better" ]
    sorted = [ "aa", "bb", "cc", "dd", "ee", "ff" ]
    reverse = [ "ff", "ee", "dd", "cc", "bb", "aa" ]
    empty = []
    flat = [ "flat", "flat", "flat", "flat", "flat" ]
    #item 182
    sorter = Sorter(string_comparer)
    unsorted2 = sorter.quick_sort(unsorted)
    sorted2 = sorter.quick_sort(sorted)
    reverse2 = sorter.quick_sort(reverse)
    empty2 = sorter.quick_sort(empty)
    flat2 = sorter.quick_sort(flat)
    #item 183
    print(str(unsorted2))
    print(str(sorted2))
    print(str(reverse2))
    print(str(empty2))
    print(str(flat2))
    #item 184
    strings_are_sorted(unsorted2)
    strings_are_sorted(sorted2)
    strings_are_sorted(reverse2)
    strings_are_sorted(empty2)
    strings_are_sorted(flat2)
    return None
    


def string_comparer(left, right):
    _next_item_ = 170
    while True:
        if _next_item_ == 170:
            if left < right:
                #item 171
                return -1
            else:
                _next_item_ = 174
    
        if _next_item_ == 174:
            if left > right:
                #item 173
                return 1
            else:
                #item 172
                return 0
    


def strings_are_sorted(array):
    _next_item_ = 201
    while True:
        if _next_item_ == 201:
            length = len(array)
            #item 1920001
            i = 0
            _next_item_ = 1920002
    
        if _next_item_ == 1920002:
            if i < length:
                #item 194
                current = array[i]
                #item 1950001
                j = i + 1
                _next_item_ = 1950002
            else:
                return None
    
        if _next_item_ == 1950002:
            if j < length:
                #item 197
                after = array[j]
                _next_item_ = 202
            else:
                #item 1920003
                i += 1
                _next_item_ = 1920002
                continue
    
        if _next_item_ == 202:
            _sw_202 = string_comparer(current, after)
            if _sw_202 == -1:
                _next_item_ = 1950003
            elif _sw_202 == 0:
                _next_item_ = 1950003
            elif _sw_202 == 1:
                #item 198
                raise Exception( "Collection is not sorted:\n" + str(array))
                return None
            else:
                raise Exception("Not expected:  " + str(_sw_202))
    
        if _next_item_ == 1950003:
            j += 1
            _next_item_ = 1950002
            continue
    

class Sorter:

    def __init__(self, comparer):
            #item 217
        self.comparer = comparer
        return None
        


    def quick_sort(self, collection):
        _next_item_ = 126
        while True:
            if _next_item_ == 126:
                length = len(collection)
        
            #item 127
                _sw_127 = length
                if _sw_127 == 0:
                    _next_item_ = 138
                elif _sw_127 == 1:
                    _next_item_ = 138
                elif _sw_127 == 2:
                    #item 143
                    first = collection[0]
                    second = collection[1]
                    _next_item_ = 144
                else:
                    #item 149
                    half = int(length / 2)
                    median = collection[half]
                    left = []
                    right = []
                    #item 1500001
                    i = 0
                    _next_item_ = 1500002
        
            if _next_item_ == 1500002:
                if i < length:
                    pass
                else:
                    #item 161
                    left_sorted = self.quick_sort(left)
                    right_sorted = self.quick_sort(right)
                    #item 162
                    result = []
                    result.extend(left_sorted)
                    result.append(median)
                    result.extend(right_sorted)
                    return result
        
            #item 163
                if i == half:
                    _next_item_ = 1500003
                else:
                    #item 152
                    current = collection[i]
                    _next_item_ = 153
        
            if _next_item_ == 153:
                if self.comparer(current, median) < 0:
                    #item 154
                    left.append(current)
                    _next_item_ = 1500003
                else:
                    #item 155
                    right.append(current)
                    _next_item_ = 1500003
        
            if _next_item_ == 1500003:
                i += 1
                _next_item_ = 1500002
                continue
        
            if _next_item_ == 144:
                if self.comparer(first, second) < 0:
                    #item 145
                    return collection
                else:
                    #item 146
                    return [ second, first ]
        
            if _next_item_ == 138:
                return collection
        

quick_sort_demo()
