You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
 
 
 
 

101 lines
2.7 KiB

#!/usr/bin/env python3
import os.path
from random import randint
import sys
SCRIPT_DIR = os.path.dirname(os.path.realpath(__file__))
class QuicksortTester (object):
def __init__(self, select_pivot):
self.select_pivot = select_pivot
self.total_comparisons = 0
def quicksort(self, word, lo, hi):
self.total_comparisons += 1
if lo < hi:
p = self.partition(word, lo, hi)
self.quicksort(word, lo, p)
self.quicksort(word, p + 1, hi)
def partition(self, word, lo, hi):
pivot = self.select_pivot(self, word, lo, hi)
i = lo - 1
j = hi + 1
while True:
while True:
i += 1
self.total_comparisons += 1
if word[i] >= pivot:
break
while True:
j -= 1
self.total_comparisons += 1
if word[j] <= pivot:
break
self.total_comparisons += 1
if i >= j:
return j
temp = word[i]
word[i] = word[j]
word[j] = temp
def test(self):
self.total_comparisons = 0
for line in open(os.path.join(SCRIPT_DIR, 'words')):
word = list(line.strip())
self.quicksort(word, 0, len(word) - 1)
assert word == list(sorted(line.strip()))
return self.total_comparisons
def first(tester, word, lo, hi):
return word[lo]
def last(tester, word, lo, hi):
return word[hi - 1]
def middle(tester, word, lo, hi):
return word[(lo+hi) // 2]
def random(tester, word, lo, hi):
return word[randint(lo, hi - 1)]
def _mid_of_three(tester, word, i, j, k):
a = word[i]
b = word[j]
c = word[k]
tester.total_comparisons += 2
if a > b:
if b > c:
return b
else:
tester.total_comparisons += 1
if a > c:
return c
else:
return a
else:
if a > c:
return a
else:
tester.total_comparisons += 1
if b > c:
return c
else:
return b
def mid_of_three(tester, word, lo, hi):
return _mid_of_three(tester, word, lo, (lo+hi) // 2, hi - 1)
def mid_of_three_rand(tester, word, lo, hi):
randoms = [randint(lo, hi - 1) for _ in range(3)]
return _mid_of_three(tester, word, *randoms)
def main():
methods = [first, last, middle, mid_of_three]
methods.extend([random]*3)
methods.extend([mid_of_three_rand]*3)
for method in methods:
print('{}: {}'.format(method.__name__, QuicksortTester(method).test()))
if __name__ == '__main__':
main()