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 ___________________-

  assist with splitting the list

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

  continue with duplicating 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.

  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 left hand 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)

  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, 19, 16, 15, 17]

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

   [9, 3, 10, 13, 12]

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

 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

  19

  16

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

  Merge Sort

  Insertion Sort

  Quick Sort

  Shell 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 x 2

  (n-3)

  (n-2)


Report an error