-
Notifications
You must be signed in to change notification settings - Fork 2
/
quicksort.py
146 lines (118 loc) · 4.05 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
#!/usr/bin/python
# Author: Arturs Polis
#
import math
import sys
import itertools
def SelectPivot(R):
"""
Cacluclate a pivot given list of strings R
Pick the last, the first, and the middle element, and choose their median as a pivot
Source: http://www.cs.utexas.edu/~lavender/courses/EE360C/lectures/lecture-22.pdf
"""
length = len(R)
i_first = 0
i_last = length-1
i_mid = int(math.ceil((length-1)/2))
#only two elements, return any:
if i_last == i_mid :
return i_first
#Otherwise, if there are three elements,
#Possible arrangements are: 123,132,213,231,312,321
if R[i_last] >= R[i_mid] : #last element is bigger than the middle: 123,213,312
if R[i_mid] >= R[i_first] : #123
return i_mid
elif R[i_first] >= R[i_last] : #312
return i_last
else : #213
return i_first
else: #last element is smaller than the middle: 132,231,321
if R[i_mid] <= R[i_first] : #321
return i_mid
elif R[i_first] <= R[i_last] : #132
return i_last
else : #231
return i_first
return None
def TernaryQuickSort(R):
"""
Performs string ternary quicksort on the strings in R
Input:
(Multi)set R in arbitrary order.
Output:
R in ascending order.
"""
length = len(R)
if length <= 1:
return R
x = SelectPivot(R)
#init empty lists
R_less = []
R_equal = []
R_greater = []
#iterate over strings in R and use Python's built-in string comparisson
for s in R :
if s < R[x] :
R_less.append(s)
elif s == R[x] :
R_equal.append(s)
else :
R_greater.append(s)
#partition the function execution into two recursive calls to TernaryQuickSort
R_less = TernaryQuickSort(R_less)
R_greater = TernaryQuickSort(R_greater)
return R_less + R_equal + R_greater
def QuickSort(iterable, depth=0):
"""
Performs string quicksort on the strings in iterable
Input:
(Multi)set iterable of strings and the length
Integer depth = position being compared, defaults to zero
Output:
iterable in ascending lexicographical order.
"""
stack = [[iterable, depth]] #recurssion stack
result = [] #store the sorted list here
while stack :
R, l = stack.pop() #get the list to sort in the current iteration, position marker being sorted
length = len(R)
#if the resulting list of strings is of length one or shorter, append it to the result
# and continue looping
if length <= 1:
if length == 1 :
result += R
continue
#init empty lists
R_less = []
R_equal = []
R_greater = []
R_new = [] #updated R
#find all elements shorter then l and append them to the result
for S in R:
if len(S) <= l :
result.append(S)
else :
R_new.append(S)
#if we have no elements in R left after the last operation - then continue to next iteration
if len(R_new) == 0 :
continue
#select a pivot
X = R_new[SelectPivot(R_new)]
char_at_x = X[l]
for S in R_new : #partition the list into smaller-than, equal, greater-than lists
if S[l] < char_at_x :
R_less.append(S)
elif S[l] == char_at_x :
R_equal.append(S)
else :
R_greater.append(S)
#create 3 stacks to iterate through - this replaces functional recurssions with parameter stack
stack.append((R_greater, l))
stack.append((R_equal, l+1))
stack.append((R_less, l))
return result
if __name__ == "__main__" :
#rudimentary test:
_R = ['abc','def', 'i', 'aaf','adsf1','gxxa','a']
print(TernaryQuickSort(_R))
print(QuickSort(_R))