# 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)