Preview

04 - Quick Sort

 1. The quick sort uses _____________ to gain the same advantages as the merge sort, while not using additional storage

  the path finding sort technique

  the A star algorithm

  heuristics

  divide and conquer

 2. A quick sort first selects a value, which is called the ________. Although there are many different ways to choose the pivot value,we often just use the first item in the list.

  mid point

  first index value

  pivot value

  binary path point

 3. The role of the pivot value is to assist The role of the pivot value is to ___________________-

  finding the first index number in the list

  assist with splitting the list

  continue with duplicating the list

  There is no such thing as a pivot value in 'quick sort'

 4. Read the excerpt below on 'partitioning' and fill in the blanks 
Partitioning begins by locating two position markers—let’s call them leftmark and rightmark—at 
the beginning and end of the remaining items in the list

The goal of the partition process is to _____________________________________________
_______________________________________________________while also converging on the split point.

  delete all the items on the left hand side of the pivot value

  move items that are on the wrong side with respect to the pivot value

  create a duplicate list on the other side of the pivot value

  delete all the items on the right hand side of the pivot value

 5. In the code shown below, it invokes a ________________________ quickSortHelper. quickSortHelper begins with the same base case as the merge sort. 
def quickSort(alist):
   quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):
   if first<last:

       splitpoint = partition(alist,first,last)

       quickSortHelper(alist,first,splitpoint-1)
       quickSortHelper(alist,splitpoint+1,last)


def partition(alist,first,last):
   pivotvalue = alist[first]

   leftmark = first+1
   rightmark = last

   done = False
   while not done:

       while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
           leftmark = leftmark + 1

       while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
           rightmark = rightmark -1

       if rightmark < leftmark:
           done = True
       else:
           temp = alist[leftmark]
           alist[leftmark] = alist[rightmark]
           alist[rightmark] = temp

   temp = alist[first]
   alist[first] = alist[rightmark]
   alist[rightmark] = temp


   return rightmark

alist = [54,26,93,17,77,31,44,55,20]
quickSort(alist)
print(alist)

  base function

  binary function

  recursive function

  iterative function

 6. Given the following list of numbers [14, 17, 13, 15, 19, 10, 3, 16, 9, 12] which answer shows the contents of the list after the second partitioning according to the quicksort algorithm?

  [9, 3, 10, 13, 12, 14, 19, 16, 15, 17]

   [9, 3, 10, 13, 12]

  [9, 3, 10, 13, 12, 14]

  [9, 3, 10, 13, 12, 14, 17, 16, 15, 19]

 7. Given the following list of numbers [1, 20, 11, 5, 2, 9, 16, 14, 13, 19] what would be the first pivot value using the median of 3 method? 
Note: Median of 3 - To choose the pivot value, we will consider the first, the middle, and the last element in the list.

  1

  19

  9

  16

 8. Which of the following sort algorithms are guaranteed to be O(n log n) even in the worst case?

  Insertion Sort

  Shell Sort

  Quick Sort

  Merge Sort

 9. The best case for quick sort occurs when the partition process always picks the middle element as pivot.

  FALSE

  TRUE

 10. In the worst case, QuickSort recursively calls one subproblem with size 0 and other subproblem with size _____________ 
Additional reading on QuickSort

  n x 2

  (n-1)

  (n-3)

  (n-2)


Report an error