-
Notifications
You must be signed in to change notification settings - Fork 7
/
QuickSort.py
152 lines (112 loc) · 4.04 KB
/
QuickSort.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
#! usr/bin/env python
"""
This is a program which implements the quicksort algorithm
in three different ways. The first takes the pivot element
to always be the first element of the array, while the second
takes the pivot to always be the last element. The third
way is to consider the first, last, and middle element of
the array and letting the pivot be the median of the three.
This saves time in arrays that are nearly sorted or nearly
reverse sorted. This program also calculates the number of
comparisons quicksort uses while sorting.
"""
firstcomparison = 0
lastcomparison = 0
mediancomparison = 0
#A method for partition around the first element of the array
def partition_first(array, leftend, rightend):
pivot = array[leftend]
i = leftend + 1
for j in range(leftend + 1, rightend):
if array[j] < pivot:
temp = array[j]
array[j] = array[i]
array[i] = temp
i += 1
leftendval = array[leftend]
array[leftend] = array[i-1]
array[i-1] = leftendval
return i - 1
#A method for partitioning around the last element of the array
def partition_last(array, leftend, rightend):
pivot = array[rightend-1]
array[rightend-1] = array[leftend]
array[leftend] = pivot
i = leftend + 1
for j in range(leftend + 1, rightend):
if array[j] < pivot:
temp = array[j]
array[j] = array[i]
array[i] = temp
i += 1
leftendval = array[leftend]
array[leftend] = array[i-1]
array[i-1] = leftendval
return i - 1
#A method to calculate the median of three numbers using two comparisons
def median(a, b, c):
if ( a - b) * (c - a) >= 0:
return a
elif (b - a) * (c - b) >= 0:
return b
else:
return c
#A method to partition around the median
def partition_median(array, leftend, rightend):
left = array[leftend]
right = array[rightend-1]
length = rightend - leftend
if length % 2 == 0:
middle = array[leftend + length/2 - 1]
else:
middle = array[leftend + length/2]
pivot = median(left, right, middle)
pivotindex = array.index(pivot) #only works if all values in array unique
array[pivotindex] = array[leftend]
array[leftend] = pivot
i = leftend + 1
for j in range(leftend + 1, rightend):
if array[j] < pivot:
temp = array[j]
array[j] = array[i]
array[i] = temp
i += 1
leftendval = array[leftend]
array[leftend] = array[i-1]
array[i-1] = leftendval
return i - 1
#Implement quicksort while partitioning around the first index
def quick_sort1(array, leftindex, rightindex):
global firstcomparison
if leftindex < rightindex:
newpivotindex = partition_first(array, leftindex, rightindex)
firstcomparison += (rightindex - leftindex - 1)
quick_sort1(array, leftindex, newpivotindex)
quick_sort1(array, newpivotindex + 1, rightindex)
def quicksort_last(array, leftindex, rightindex):
global lastcomparison
if leftindex < rightindex:
newpivotindex = partition_last(array, leftindex, rightindex)
lastcomparison += (rightindex - leftindex - 1)
quicksort_last(array, leftindex, newpivotindex)
quicksort_last(array, newpivotindex + 1, rightindex)
def quicksort_median(array, leftindex, rightindex):
global mediancomparison
if leftindex < rightindex:
newpivotindex = partition_median(array, leftindex, rightindex)
mediancomparison += (rightindex - leftindex - 1)
quicksort_median(array, leftindex, newpivotindex)
quicksort_median(array, newpivotindex + 1, rightindex)
test3 = [1, 11, 5, 15, 2, 12, 9, 99, 77, 0]
test4 = []
for i in range(1, 101):
test4.append(i)
f = open("IntegerArray.txt", "r")
intarray = []
for line in f:
intarray.append(int(line))
f.close()
#test on an array of length 10000
mediancomparison = 0
quicksort_median(intarray, 0, len(intarray))
print mediancomparison