The questions
1.
Your task is to compute the total number of comparisons used to sort the given input file by QuickSort. As you know, the number of comparisons depends on which elements are chosen as pivots, so we'll ask you to explore three different pivoting rules.
You should not count comparisons one-by-one. Rather, when there is a recursive call on a subarray of length m, you should simply add m−1 to your running total of comparisons. (This is because the pivot element is compared to each of the other m−1 elements in the subarray in this recursive call.)
WARNING: The Partition subroutine can be implemented in several different ways, and different implementations can give you differing numbers of comparisons. For this problem, you should implement the Partition subroutine exactly as it is described in the video lectures (otherwise you might get the wrong answer).
DIRECTIONS FOR THIS PROBLEM:
For the first part of the programming assignment, you should always use the first element of the array as the pivot element.
2. Compute the number of comparisons (as in Problem 1), always using the final element of the given array as the pivot element. Again, be sure to implement the Partition subroutine exactlyas it is described in the video lectures.
Recall from the lectures that, just before the main Partition subroutine, you should exchange the pivot element (i.e., the last element) with the first element.
3. Compute the number of comparisons (as in Problem 1), using the "median-of-three" pivot rule. [The primary motivation behind this rule is to do a little bit of extra work to get much better performance on input arrays that are nearly sorted or reverse sorted.] In more detail, you should choose the pivot as follows. Consider the first, middle, and final elements of the given array. (If the array has odd length it should be clear what the "middle" element is; for an array with even length
2k, use the kth element as the "middle" element. So for the array 4 5 6 7, the "middle" element is the second one ---- 5 and not 6!) Identify which of these three elements is the median (i.e., the one whose value is in between the other two), and use this as your pivot. As discussed in the first and second parts of this programming assignment, be sure to implement Partition exactly as described in the video lectures (including exchanging the pivot element with the first element just before the main Partition subroutine).
EXAMPLE: For the input array 8 2 4 5 7 1 you would consider the first (8), middle (4), and last (1) elements; since 4 is the median of the set {1,4,8}, you would use 4 as your pivot element.
SUBTLE POINT: A careful analysis would keep track of the comparisons made in identifying the median of the three candidate elements. You should NOT do this. That is, as in the previous two problems, you should simply add m−1 to your running total of comparisons every time you recurse on a subarray with length m.
My answers:
1.
#quicksort using first element of array as the pivot
def partition(A, l, r):
piv = A[l];
i = l+1
for j in range(l+1, r):
if A[j] <piv:
A[j], A[i] = A[i], A[j]
i = i+1
A[l], A[i-1] = A[i-1], A[l] #swap pivot into rightful place
return i
def quickSort(A, l, r):
count = 0
if l<r:
count = r-l-1
split = partition(A,l,r)
lc = quickSort(A,l,split-1) #during the for loop, this ends one before pivot
rc = quickSort(A,split,r) #because the split is the lower bound, syntax of for loop makes it one after the pivot
return count +lc +rc
else:
return 0
inFile = open("quickSort.txt", 'r')
with inFile as f:
numList = [int(integers.strip()) for integers in f.readlines()]
# numList = [line.rstrip() for line in open('quickSort.txt')] <- Doesn't work
tot = quickSort(numList, 0, len(numList))
print tot
2.
#quicksort using last element of array as the pivot
def partition(A, l, r):
piv = A[l];
i = l+1
for j in range(l+1, r):
if A[j] <piv:
A[j], A[i] = A[i], A[j]
i = i+1
A[l], A[i-1] = A[i-1], A[l] #swap pivot into rightful place
return i
def quickSort(A, l, r):
count = 0
if l<r:
A[l], A[r-1]= A[r-1], A[l]
count = r-l-1
split = partition(A,l,r)
lc = quickSort(A,l,split-1) #during the for loop, this ends one before pivot
rc = quickSort(A,split,r) #because the split is the lower bound, syntax of for loop makes it one after the pivot
return count +lc +rc
else:
return 0
inFile = open("quickSort.txt", 'r')
with inFile as f:
numList = [int(integers.strip()) for integers in f.readlines()]
tot = quickSort(numList, 0, len(numList))
print tot
3.
#quicksort using median of three as pivot
def partition(A, l, r):
piv = A[l];
i = l+1
for j in range(l+1, r):
if A[j] <piv:
A[j], A[i] = A[i], A[j]
i = i+1
A[l], A[i-1] = A[i-1], A[l] #swap pivot into rightful place
return i
def isMedian(a,b,c):
if(a<=b and b<=c) or (a>=b and b>=c):
return True
def quickSort(A, l, r):
count = 0
if l<r:
mid = l + (r-l+1)/2 - 1 #find out middle element
if isMedian(A[l], A[mid], A[r-1]):
A[l], A[mid] = A[mid], A[l] #switch middle (if it is median) to be the first element and use as pivot
elif isMedian(A[l], A[r-1], A[mid]):
A[l], A[r-1]= A[r-1], A[l] #switch last (if it is median) to be first element and use as pivot
count = r-l-1
split = partition(A,l,r)
lc = quickSort(A,l,split-1) #during the for loop, this ends one before pivot
rc = quickSort(A,split,r) #because the split is the lower bound, syntax of for loop makes it one after the pivot
return count +lc +rc
else:
return 0
NUMLIST_FILENAME = "quickSort.txt"
inFile = open(NUMLIST_FILENAME, 'r')
with inFile as f:
numList = [int(integers.strip()) for integers in f.readlines()]
# numList = [line.rstrip() for line in open('integerArray.txt')]
tot = quickSort(numList, 0, len(numList))
print tot
