Computing Work Done (Total Comparisons) by Quick Sort
#!/usr/bin/env | |
# Case I | |
# First element of the unsorted array is chosen as pivot element for sorting using Quick Sort | |
def countComparisonsWithFirst(x): | |
""" Counts number of comparisons while using Quick Sort with first element of unsorted array as pivot """ | |
global count_pivot_first | |
if len(x) == 1 or len(x) == 0: | |
return x | |
else: | |
count_pivot_first += len(x)-1 | |
i = 0 | |
for j in range(len(x)-1): | |
if x[j+1] < x[0]: | |
x[j+1],x[i+1] = x[i+1], x[j+1] | |
i += 1 | |
x[0],x[i] = x[i],x[0] | |
first_part = countComparisonsWithFirst(x[:i]) | |
second_part = countComparisonsWithFirst(x[i+1:]) | |
first_part.append(x[i]) | |
return first_part + second_part | |
# Case II | |
# Last element of the unsorted array is chosen as pivot element for sorting using Quick Sort | |
def countComparisonsWithLast(x): | |
""" Counts number of comparisons while using Quick Sort with last element of unsorted array as pivot """ | |
global count_pivot_last | |
if len(x) == 1 or len(x) == 0: | |
return x | |
else: | |
count_pivot_last += len(x)-1 | |
x[0],x[-1] = x[-1],x[0] | |
i = 0 | |
for j in range(len(x)-1): | |
if x[j+1] < x[0]: | |
x[j+1],x[i+1] = x[i+1], x[j+1] | |
i += 1 | |
x[0],x[i] = x[i],x[0] | |
first_part = countComparisonsWithLast(x[:i]) | |
second_part = countComparisonsWithLast(x[i+1:]) | |
first_part.append(x[i]) | |
return first_part + second_part | |
# Case III | |
# Median-of-three method used to choose pivot element for sorting using Quick Sort | |
def middle_index(x): | |
""" Returns the index of the middle element of an array """ | |
if len(x) % 2 == 0: | |
middle_index = len(x)/2 - 1 | |
else: | |
middle_index = len(x)/2 | |
return middle_index | |
def median_index(x,i,j,k): | |
""" Returns the median index of three when passed an array and indices of any 3 elements of that array """ | |
if (x[i]-x[j])*(x[i]-x[k]) < 0: | |
return i | |
elif (x[j]-x[i])*(x[j]-x[k]) < 0: | |
return j | |
else: | |
return k | |
def countComparisonsMedianOfThree(x): | |
""" Counts number of comparisons while using Quick Sort with median-of-three element is chosen as pivot """ | |
global count_pivot_median | |
if len(x) == 1 or len(x) == 0: | |
return x | |
else: | |
count_pivot_median += len(x)-1 | |
k = median_index(x, 0, middle_index(x), -1) | |
if k != 0: x[0], x[k] = x[k], x[0] | |
i = 0 | |
for j in range(len(x)-1): | |
if x[j+1] < x[0]: | |
x[j+1],x[i+1] = x[i+1], x[j+1] | |
i += 1 | |
x[0],x[i] = x[i],x[0] | |
first_part = countComparisonsMedianOfThree(x[:i]) | |
second_part = countComparisonsMedianOfThree(x[i+1:]) | |
first_part.append(x[i]) | |
return first_part + second_part | |
##################################################################### | |
# initializing counts | |
count_pivot_first = 0; count_pivot_last = 0; count_pivot_median = 0 | |
##################################################################### | |
# Cast I | |
# Read the contents of the file into a Python list | |
NUMLIST_FILENAME = "QuickSort_List.txt" | |
inFile = open(NUMLIST_FILENAME, 'r') | |
with inFile as f: numList = [int(integers.strip()) for integers in f.readlines()] | |
# call functions to count comparisons | |
countComparisonsWithFirst(numList) | |
##################################################################### | |
# Read the contents of the file into a Python list | |
NUMLIST_FILENAME = "QuickSort_List.txt" | |
inFile = open(NUMLIST_FILENAME, 'r') | |
with inFile as f: numList = [int(integers.strip()) for integers in f.readlines()] | |
# call functions to count comparisons | |
countComparisonsWithLast(numList) | |
##################################################################### | |
# Read the contents of the file into a Python list | |
NUMLIST_FILENAME = "QuickSort_List.txt" | |
inFile = open(NUMLIST_FILENAME, 'r') | |
with inFile as f: numList = [int(integers.strip()) for integers in f.readlines()] | |
# call functions to count comparisons | |
countComparisonsMedianOfThree(numList) | |
##################################################################### | |
print count_pivot_first, count_pivot_last, count_pivot_median |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment