-
Notifications
You must be signed in to change notification settings - Fork 50
/
Copy pathsorting.py
190 lines (155 loc) · 8.64 KB
/
sorting.py
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
#!python
def is_sorted(items):
"""Return a boolean indicating whether given items are in sorted order.
TODO: Running time: ??? Why and under what conditions?
TODO: Memory usage: ??? Why and under what conditions?"""
# TODO: Check that all adjacent items are in order, return early if not
def bubble_sort(items):
"""Sort given items by swapping adjacent items that are out of order, and
repeating until all items are in sorted order.
TODO: Running time: ??? Why and under what conditions?
TODO: Memory usage: ??? Why and under what conditions?"""
# TODO: Repeat until all items are in sorted order
# TODO: Swap adjacent items that are out of order
def selection_sort(items):
"""Sort given items by finding minimum item, swapping it with first
unsorted item, and repeating until all items are in sorted order.
TODO: Running time: ??? Why and under what conditions?
TODO: Memory usage: ??? Why and under what conditions?"""
# TODO: Repeat until all items are in sorted order
# TODO: Find minimum item in unsorted items
# TODO: Swap it with first unsorted item
def insertion_sort(items):
"""Sort given items by taking first unsorted item, inserting it in sorted
order in front of items, and repeating until all items are in order.
TODO: Running time: ??? Why and under what conditions?
TODO: Memory usage: ??? Why and under what conditions?"""
# TODO: Repeat until all items are in sorted order
# TODO: Take first unsorted item
# TODO: Insert it in sorted order in front of items
def merge(items1, items2):
"""Merge given lists of items, each assumed to already be in sorted order,
and return a new list containing all items in sorted order.
TODO: Running time: ??? Why and under what conditions?
TODO: Memory usage: ??? Why and under what conditions?"""
# TODO: Repeat until one list is empty
# TODO: Find minimum item in both lists and append it to new list
# TODO: Append remaining items in non-empty list to new list
def split_sort_merge(items):
"""Sort given items by splitting list into two approximately equal halves,
sorting each with an iterative sorting algorithm, and merging results into
a list in sorted order.
TODO: Running time: ??? Why and under what conditions?
TODO: Memory usage: ??? Why and under what conditions?"""
# TODO: Split items list into approximately equal halves
# TODO: Sort each half using any other sorting algorithm
# TODO: Merge sorted halves into one list in sorted order
def merge_sort(items):
"""Sort given items by splitting list into two approximately equal halves,
sorting each recursively, and merging results into a list in sorted order.
TODO: Running time: ??? Why and under what conditions?
TODO: Memory usage: ??? Why and under what conditions?"""
# TODO: Check if list is so small it's already sorted (base case)
# TODO: Split items list into approximately equal halves
# TODO: Sort each half by recursively calling merge sort
# TODO: Merge sorted halves into one list in sorted order
def partition(items, low, high):
"""Return index `p` after in-place partitioning given items in range
`[low...high]` by choosing a pivot (TODO: document your method here) from
that range, moving pivot into index `p`, items less than pivot into range
`[low...p-1]`, and items greater than pivot into range `[p+1...high]`.
TODO: Running time: ??? Why and under what conditions?
TODO: Memory usage: ??? Why and under what conditions?"""
# TODO: Choose a pivot any way and document your method in docstring above
# TODO: Loop through all items in range [low...high]
# TODO: Move items less than pivot into front of range [low...p-1]
# TODO: Move items greater than pivot into back of range [p+1...high]
# TODO: Move pivot item into final position [p] and return index p
def quick_sort(items, low=None, high=None):
"""Sort given items in place by partitioning items in range `[low...high]`
around a pivot item and recursively sorting each remaining sublist range.
TODO: Best case running time: ??? Why and under what conditions?
TODO: Worst case running time: ??? Why and under what conditions?
TODO: Memory usage: ??? Why and under what conditions?"""
# TODO: Check if high and low range bounds have default values (not given)
# TODO: Check if list or range is so small it's already sorted (base case)
# TODO: Partition items in-place around a pivot and get index of pivot
# TODO: Sort each sublist range by recursively calling quick sort
def counting_sort(numbers):
"""Sort given numbers (integers) by counting occurrences of each number,
then looping over counts and copying that many numbers into output list.
TODO: Running time: ??? Why and under what conditions?
TODO: Memory usage: ??? Why and under what conditions?"""
# TODO: Find range of given numbers (minimum and maximum integer values)
# TODO: Create list of counts with a slot for each number in input range
# TODO: Loop over given numbers and increment each number's count
# TODO: Loop over counts and append that many numbers into output list
# FIXME: Improve this to mutate input instead of creating new output list
def bucket_sort(numbers, num_buckets=10):
"""Sort given numbers by distributing into buckets representing subranges,
sorting each bucket, and combining contents of all buckets in sorted order.
TODO: Running time: ??? Why and under what conditions?
TODO: Memory usage: ??? Why and under what conditions?"""
# TODO: Find range of given numbers (minimum and maximum integer values)
# TODO: Create list of buckets to store numbers in subranges of input range
# TODO: Loop over given numbers and place each item in appropriate bucket
# TODO: Sort each bucket using any sorting algorithm (recursive or another)
# TODO: Loop over buckets and append each bucket's numbers into output list
# FIXME: Improve this to mutate input instead of creating new output list
def random_ints(count=20, min=1, max=50):
"""Return a list of `count` integers sampled uniformly at random from
given range [`min`...`max`] with replacement (duplicates are allowed)."""
import random
return [random.randint(min, max) for _ in range(count)]
def test_sorting(sort=bubble_sort, num_items=20, max_value=50):
"""Test sorting algorithms with a small list of random items."""
# Create a list of items randomly sampled from range [1...max_value]
items = random_ints(num_items, 1, max_value)
print('Initial items: {!r}'.format(items))
print('Sorted order? {!r}'.format(is_sorted(items)))
# Change this sort variable to the sorting algorithm you want to test
# sort = bubble_sort
print('Sorting items with {}(items)'.format(sort.__name__))
sort(items)
print('Sorted items: {!r}'.format(items))
print('Sorted order? {!r}'.format(is_sorted(items)))
def main():
"""Read command-line arguments and test sorting algorithms."""
import sys
args = sys.argv[1:] # Ignore script file name
if len(args) == 0:
script = sys.argv[0] # Get script file name
print('Usage: {} sort num max'.format(script))
print('Test sorting algorithm `sort` with a list of `num` integers')
print(' randomly sampled from the range [1...`max`] (inclusive)')
print('\nExample: {} bubble_sort 10 20'.format(script))
print('Initial items: [3, 15, 4, 7, 20, 6, 18, 11, 9, 7]')
print('Sorting items with bubble_sort(items)')
print('Sorted items: [3, 4, 6, 7, 7, 9, 11, 15, 18, 20]')
return
# Get sort function by name
if len(args) >= 1:
sort_name = args[0]
# Terrible hack abusing globals
if sort_name in globals():
sort_function = globals()[sort_name]
else:
# Don't explode, just warn user and show list of sorting functions
print('Sorting function {!r} does not exist'.format(sort_name))
print('Available sorting functions:')
for name in globals():
if name.find('sort') >= 0:
print(' {}'.format(name))
return
# Get num_items and max_value, but don't explode if input is not an integer
try:
num_items = int(args[1]) if len(args) >= 2 else 20
max_value = int(args[2]) if len(args) >= 3 else 50
# print('Num items: {}, max value: {}'.format(num_items, max_value))
except ValueError:
print('Integer required for `num` and `max` command-line arguments')
return
# Test sort function
test_sorting(sort_function, num_items, max_value)
if __name__ == '__main__':
main()