Computing Work Done (Total Comparisons) by Quick Sort
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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