# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python [conda env:py35]
#     language: python
#     name: conda-env-py35-py
# ---

# ### Play with various sorts
#
# Evaluate various sorts.
#
# See [Instertion Sort example](http://www.geekviewpoint.com/python/sorting/insertionsort)

# +
debugging = False
debugging = True

logging = True

def dbg(f, *args):
    if debugging:
        print(('  DBG:' + f).format(*args))

def log(f, *args):
    if logging:
        print((f).format(*args))
        
def logError(f, *args):
    if logging:
        print(('*** ERROR:' + f).format(*args))
        
def className(instance):
    return type(instance).__name__
# -

# ### The TestSet Mechanism

# # %load TestHarness.py




# ### The Unit Under Test

#=======================================================================
#  Author: <NAME>
#  Title: Insertionsort
#  Project: geekviewpoint
#  Package: algorithms
#
#  Statement:
#  Given a disordered list of integers (or any other items),
#  rearrange the integers in natural order.
#
#  Sample Input: [8,5,3,1,9,6,0,7,4,2,5]
#  Sample Output: [0,1,2,3,4,5,5,6,7,8,9]
#
#  Time Complexity of Solution:
#  Best O(n); Average O(n^2); Worst O(n^2).
#
#  Approach:
#  Insertion sort is good for collections that are very small
#  or nearly sorted. Otherwise it's not a good sorting algorithm:
#  it moves data around too much. Each time an insertion is made,
#  all elements in a greater position are shifted.
#======================================================================= 
def insertionsort( aList ):
    for i in range( 1, len( aList ) ):
        tmp = aList[i]
        k = i
        dbg('--- i={0} tmp={1} aList={2}', i, tmp, aList)
        while k > 0 and tmp < aList[k - 1]:
            aList[k] = aList[k - 1]
            k -= 1
        aList[k] = tmp



a = [8,5,3,1,9,6,0,7,4,2,5]
bubbleSort(a)
a


#=======================================================================
#  BubbleSort
#
#  Time Complexity of Solution:
#  Best O(n); Average O(n^2); Worst O(n^2).
#
#  Approach:
#  Bubble sort is goodf for very small collections that are almost
#  already sorted. 
#======================================================================= 
def bubbleSort( a ):
    m = len(a) - 1
    swapped = True
    def swap(i, j):
        nonlocal swapped
        t = a[i]
        a[i] = a[j]
        a[j] = t
        swapped = True
    while swapped:
        swapped = False
        dbg('--- m={0} a={1}', m, a)        
        for i in range( 0, m ):
            if a[i] > a[i+1]:
                swap(i, i+1)
        m -= 1 # Ass end is sorted already.



#=======================================================================
#  QuickSort
#
#  Time Complexity of Solution:
#  Best O(n); Average O(n*logn); Worst O(n^2).
#
#  Approach:
#  Quick sort is good for non pathological lists
#======================================================================= 
def quickSort( a ):
    def sortPartition(i, j, name):
        def swap(i, j):
            t = a[i]
            a[i] = a[j]
            a[j] = t        
        # A single element is always sorted.
        if j - i < 1:
            return
        # Any two elements are easily sorted.
        if j - i == 1:
            if a[i] > a[j]: swap(i, j)
            return
        pivot = a[i] # Select an arbitrary value.
        leftFence  = i+1 # Exclude the pivot value
        rightFence = j
        while leftFence <= rightFence and a[leftFence]  <= pivot : leftFence  += 1
        while leftFence <= rightFence and a[rightFence] >= pivot : rightFence -= 1
        if leftFence < rightFence: swap(leftFence, rightFence)
        swap(i, rightFence) # Relocate the pivot to the center
        sortPartition(i, rightFence-1, 'left')
        sortPartition(rightFence+1, j, 'right')
        
    sortPartition(0, len(a)-1, 'starting')


a = [5,8,3,1,9,6,0,213,1,2,41,1,423,1,21,3,1,22,1,2,4,6,33,1,7,4,2]
quickSort(a)
a

a = [2, 1, 1, 1, 1, 2]
quickSort(a)
a


# ### The Test Cases

# +
#simpletest = lambda A : [spiral_square(A)]
def simpletest(A):   
    l = [x for x in spiral_square2(A)]
    return l

A2 = [[1, 2], [3, 4]]
A3 = [[1, 2, 3], 
      [4, 5, 6], 
      [7, 8, 9]]
A4 = [[ 1,  2,  3,  4], 
      [ 5,  6,  7,  8],
      [ 9, 10, 11, 12],
      [13, 14, 15, 16]]
A4A = ['good men to come'.split(), 
       'all now is to'.split(), 
       'for time the the'.split(), 
       'country their of aid'.split()]
A5 = [[1, 2, 3, 4, 100], [5, 6, 7, 8, 200], [9, 10, 11, 12, 300], [13, 14, 15, 16, 400], [17, 18, 19, 20, 500]]

c0 = TestCase('0x0', 
              simpletest,
              [ [] ],
              [])

c1 = TestCase('1x1', 
              simpletest,
              [ [[1]] ],
              [1])

c2 = TestCase('2x2', 
              simpletest,
              [A2],
              [1, 2, 4, 3])


c3 = TestCase('3x3', 
              simpletest,
              [A3],
              [5, 4, 1, 2, 3, 6, 9, 8, 7])

c4 = TestCase('4x4', 
              simpletest,
              [A4],
              [6, 7, 11, 10, 9, 5, 1, 2, 3, 4, 8, 12, 16, 15, 14, 13])

c4a = TestCase('4x4 words', 
              simpletest,
              [A4A],
              'now is the time for all good men to come to the aid of their country'.split())

tester = TestSet([c0, c1, c2, c3, c4, c4a])

# -

tester.run_tests()



# ### Some Ad Hoc Tests

[x for x in spiral_square(A3)]

(.33333333333333333333333333333).as_integer_ratio()

(1/3).as_integer_ratio()

from fractions import Fraction
Fraction(0.333333333333333).limit_denominator()



StarcoderdataJupyterScriptsDedupFiltered