EECS281 Data Structures and Algorithms
Sorting Questions for Midterm Review
1) The following are multiple choice questions. Only one answer is correct. Circle the correct
answer. Each problem is worth 2 pts.
For the best implementation of bubble sort discussed in class, an approximation of the number of
comparisons and exchanges to sort an array of size N is:
a) N2/4 comparisons, N2/4 exchanges b) N2/2 comparisons, N2/2 exchanges
c) N2/2 comparisons, N2/4 exchanges d) N2/4 comparisons, N2/2 exchanges
e) N2/2 comparisons, N exchanges
For the best implementation of selection sort discussed in class, an approximation of the number of
comparisons and exchanges to sort an array of size N is:
a) N2/4 comparisons, N2/4 exchanges b) N2/2 comparisons, N2/2 exchanges
c) N2/2 comparisons, N2/4 exchanges d) N2/4 comparisons, N2/2 exchanges
e) N2/2 comparisons, N exchanges
For the best implementation of insertion sort discussed in class, an approximation of the number of
comparisons and exchanges to sort an array of size N is:
a) N2/4 comparisons, N2/4 exchanges b) N2/2 comparisons, N2/2 exchanges
c) N2/2 comparisons, N2/4 exchanges d) N2/4 comparisons, N2/2 exchanges
e) N2/2 comparisons, N exchanges
For the implementation of quick sort discussed in class, the worst case complexity for sorting an array
of size N is:
a) O(1) b) O(logN) c) O(N) d) O(NlogN) e) O(N2) f) O(2N)
For the implementation of quick sort discussed in class, the average case complexity for sorting an
array of size N is:
a) O(1) b) O(logN) c) O(N) d) O(NlogN) e) O(N2) f) O(2N)
For the implementation of heap sort discussed in class, the worst case complexity for sorting an array
of size N is:
a) O(1) b) O(logN) c) O(N) d) O(NlogN) e) O(N2) f) O(2N)
For the implementation of a heap discussed in class, the worst case complexity for inserting a single
item into the heap of size N is:
a) O(1) b) O(logN) c) O(N) d) O(NlogN) e) O(N2) f) O(2N)
2) Assume the following pseudocode implementation of Partition and QuickSort:
Algorithm Partition(a, left, right)
Input: array a of distinct elements, integers left and right
Output: integer
p <- a[right], lhs <- left, rhs <- right-1
while lhs ≤ rhs do
while lhs ≤ rhs and a[lhs] ≤ p do
lhs = lhs + 1
while rhs ≥ lhs and a[rhs] ≥ p do
rhs = rhs -1
if lhs < rhs then
swap(a[lhs],a[rhs])
swap(a[lhs],a[right])
return lhs
Algorithm QuickSort(a[], left, right)
Input: array a of distinct elements,
integers left and right
Output: sorted array a
if left ≥ right then return
pivot <- Partition(a, left, right)
QuickSort(a, left, pivot-1)
QuickSort(a, pivot+1, right)
Show the effect of QuickSort on the following array a. Show the array after each call to
Partition and indicate the final placement of pivots.
a = {13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21}
• gray box indicates pivot placement
• following solution assumes recursion down lhs and rhs subtrees proceeds concurrently
Init 13 19 9 5 12 8 7 4 11 2 6 21
It1 13 19 9 5 12 8 7 4 11 2 6 21
It2 2 4 5 6 12 8 7 19 11 13 9 21
It3 2 4 5 6 7 8 9 19 11 13 12 21
It4 2 4 5 6 7 8 9 11 12 13 19 21
It5 2 4 5 6 7 8 9 11 12 13 19 21
Itn 2 4 5 6 7 8 9 11 12 13 19 21
3) Assume that Quicksort uses the last item in the list as the pivot (as described earlier):
a) Give a list of 10 integers representing the worst-case scenario.
Any example with already sorted data, e.g., a = {1,2,3,4,5,6,7,8,9,10}
b) Give a list of 10 integers representing the best-case scenario.
Any example with pivot as median of each partition, e.g., a = {2,1,5,4,3,7,8,10,9,6}
Note this problem is difficult to show exact correct answer
4) Text, Problem C-10.10, Page 528. For simplicity, assume that each candidate receives a unique
number of votes. The function description is as follows:
Algorithm findPrez(S,n)
Input: integer array S of size n, integer n
Output: integer winner
QuickSort(S, 0, n-1)
//assume we use Quicksort found later in homework. Note
QuickSort() is O(n2) worst case. Therefore, might want to use
O(nlgn) best/avg/worst case sorting algorithm, like mergesort or
heapsort.
contender <- S[0]
votes <- 1
maxvotes <- 1
for i <- 1 to n-1 do //O(n)
if S[i] = contender then
votes <- votes + 1
else
if votes > maxvotes then
maxvotes <- votes
winner <- contender
contender <- S[i]
votes <- 1
Idea is as follows:
• sort S using O(nlgn) sort
• find S[i] with most occurrences in sorted S