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.

  binary path point

  mid point

  pivot value

  first index value

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

  continue with duplicating the list

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

  assist with splitting the list

  finding the first index number in the list

 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

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

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

  move items that are on the wrong side with respect to 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)

  recursive function

  iterative function

  base function

  binary 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]

   [9, 3, 10, 13, 12]

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

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

 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

  9

  16

  19

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

  Shell Sort

  Merge Sort

  Quick Sort

  Insertion 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-1)

  (n-3)

  n x 2

  (n-2)