-
Notifications
You must be signed in to change notification settings - Fork 0
/
counting_quad_sorts.py
105 lines (86 loc) · 2.72 KB
/
counting_quad_sorts.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
"""
This module contains four sorting algorithms which
can be used in other models to generate empirical data.
"""
def bubbleSort(items):
"""
Orders the items from lowest to highest value
Parameters: items - list to be sorted
Returns: count - number of times the loop has been iterated
"""
swapped = True
count = 0
while swapped:
swapped = False
for i in range(1,len(items)):
if items[i-1] > items[i]:
items[i-1], items[i] = items[i], items[i-1] # Swap values
swapped = True
count += 1
return count
def optimizedBubbleSort(items):
"""
Optimized version of classic bubble sort which
orders the items from lowest to highest value
Parameters: items - list to be sorted
Returns: count - number of times the loop has been iterated
"""
count = 0
n = len(items)
swapped = True
while swapped:
count += 1
swapped = False
for i in range(1, n):
count += 1
if items[i-1] > items[i]:
items[i-1], items[i] = items[i], items[i-1]
swapped = True
n -= 1
return count
def selectionSort(items):
"""
Orders the items from lowest to highest value
Parameters: items - list to be sorted
Returns: count - number of times the loop has been iterated
"""
count = 0 # for analysis only
n = len(items)
for i in range(n-1):
count += 1
min = i
for j in range(i + 1,n):
if (items[j] < items[min]):
min = j
count += 1
if (min != i):
items[i], items[min] = items[min], items[i] # Swap Values
return count
def insertionSort(items):
"""
Orders the items from lowest to highest value
Parameters: items - list to be sorted
Returns: count - number of times the loop has been iterated
"""
count = 0
# Traverse from 1 to the length of the list.
for i in range(1, len(items)):
count += 1
key = items[i]
# Move elements of arr[0..i-1], that are
# greater than key, to one position ahead
# of their current position
j = i-1
while j >= 0 and key < items[j]:
count += 1
items[j + 1] = items[j]
j -= 1
items[j + 1] = key
return count
if __name__ == '__main__':
print(bubbleSort([9,8,7,6,5,4,3,2,1]))
print(optimizedBubbleSort([9,8,7,6,5,4,3,2,1]))
print(selectionSort([9,8,7,6,5,4,3,2,1]))
print(insertionSort([9,8,7,6,5,4,3,2,1]))
# The above code prints the loop iterations ('count')
# for each of the 4 sorting algorithms.