122COM_sorting_algorithms/lab_sorting.py at master · covcom/122COM_sorting_algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#!/usr/bin/python3

def bubble_sort( sequence ):
    # COMPLETE ME - Green task

    return sequence

def selection_sort( sequence ):
    # COMPLETE ME - Yellow task

    return sequence

def quick_sort( sequence ):
    # COMPLETE ME - Yellow task

    return sequence

def quick_sort_inplace( sequence, start=None, end=None ):
    # COMPLETE ME - Red task

    return sequence

def merge_sort( sequence ):
    # COMPLETE ME - Red task

    return sequence


if __name__ == '__main__':
    import random, copy, sys

    class Test(object):
        def __init__(self, n, f ):
            self.name = n
            self.function = f
            self.success = False

    sortingAlgorithms = [ Test('bubblesort', bubble_sort),
                          Test('selection sort', selection_sort),
                          Test('quicksort', quick_sort),
                          Test('quick inplace', quick_sort_inplace),
                          Test('merge sort', merge_sort)]

    # ==============================================
    #    This is the small collection of numbers test
    # ==============================================
    # generate 10 random numbers between -100 and 100 so we can see that it's working
    smallNumbers = [ random.randint(-100,100) for i in range(10) ]

    # print out the small numbers
    print( 'SMALL SEQUENCE TEST' )
    print( 'starting numbers:', smallNumbers )

    # sort the small numbers
    smallCorrect = sorted( smallNumbers )
    print( 'correctly sorted:', smallCorrect )

    for test in sortingAlgorithms:
        result = test.function( copy.copy(smallNumbers) )
        print( '%s:' % test.name.rjust(16), result )

        # record if the test was a success
        test.success = result == smallCorrect

    for test in sortingAlgorithms:
        print( test.name, "worked" if test.success else "failed" )

    print()

    # ==============================================
    #    This is the big collection of numbers test
    # ==============================================
    # generate 5000 random numbers so we can profile our code
    bigNumbers = [ random.random() for i in range(5000) ]

    print( 'BIG SEQUENCE TEST' )

    # sort the big numbers
    bigCorrect = sorted( bigNumbers )

    for test in sortingAlgorithms:
        if not test.success:
            continue

        result = test.function(bigNumbers)

        test.sucess = result == bigCorrect

    for test in sortingAlgorithms:
        print( test.name, "worked" if test.success else "failed" )

    sys.exit( len([ test for test in sortingAlgorithms if test.success ]) )