Quick sort in pseudocode

Name:

Date:

Class:

Quick Questions

Shade in the A or B circle for each question.

1. Which function header correctly starts a pseudocode quick sort that takes an array?

A define quickSort(array)

B define quickSort()

2. What is the first main step inside quickSort after checking the array size?

A Choose a pivot value from the array

B Join the array back together

3. After partitioning around the pivot, where do the values go?

A Smaller values to one part, larger values to the other

B All values stay in one part with the pivot

4. Which is the correct base case for quickSort?

A if length of array = 5 then return array

B if length of array <= 1 then return array

5. How does quickSort sort each part after partitioning?

A It calls a different function on the whole array again

B It calls itself on the smaller part and the larger part

Match the Pairs

Draw a line connecting each item on the left to its match on the right.

Left column		Right column
1define quickSort(array)		AThe pivot is left out of the result, so it is lost from the sorted array. It should be quickSort(smaller) + [pivot] + quickSort(larger).
2quickSort(smaller)		Bif item < pivot then add item to smaller
3Partition step: values smaller than the pivot are placed in a separate array		CThe function header: it names the function quickSort and takes the array to be sorted as a parameter
4Base case: an array with 0 or 1 items is already sorted, so the function stops calling itself		DA recursive call that sorts the part of the array holding values less than the pivot
5define quickSort(array) pivot <- array[0] smaller <- quickSort(smaller) larger <- quickSort(larger)		EThere is no base case, so the function never stops calling itself and the recursion is infinite. It also calls quickSort on arrays that were never partitioned. Add a check for length <= 1 and partition before the calls.
6return quickSort(smaller) + quickSort(larger)		Fif length(array) <= 1 then return array

Definitions

quickSort(array)

Fill in the Blanks

Complete each line of code by filling in the missing parts.

define quickSort(_____)

if length(array) __ 1 then return array

pivot ← array[_]

for each item in rest if item _ pivot then add item to smaller

left ← quickSort(smaller) right ← _________(larger) return left + [pivot] + right

Spot the Error

Shade in the letter of the line that contains an error.

Question 1

A pivot <- array[0]

B smaller <- []

C larger <- []

D for each x in array

E if x < pivot then

F append x to smaller

Question 2

A function quickSort()

B pivot <- array[0]

C partition rest by pivot

D lo <- quickSort(smaller)

E hi <- quickSort(larger)

F return lo + [pivot] + hi

Question 3

A function split(array pivot)

B small <- items below pivot

C large <- items above pivot

D return small, large

Question 4

A function quickSort(array)

B if length(array) >= 1 then

C return array

D end if

E pivot <- array[0]

F smaller <- []

Question 5

A function quickSort(array)

B pivot <- array

C smaller <- []

D larger <- []

E // partition the rest next

Answer Key

Quick sort in pseudocode

Section A: Quick Questions

A — define quickSort(array)

A — Choose a pivot value from the array

A — Smaller values to one part, larger values to the other

B — if length of array <= 1 then return array

B — It calls itself on the smaller part and the larger part

Section B: Match the Pairs

define quickSort(array) → The function header: it names the function quickSort and takes the array to be sorted as a parameter

quickSort(smaller) → A recursive call that sorts the part of the array holding values less than the pivot

Partition step: values smaller than the pivot are placed in a separate array → if item < pivot then add item to smaller

Base case: an array with 0 or 1 items is already sorted, so the function stops calling itself → if length(array) <= 1 then return array

define quickSort(array) pivot <- array[0] smaller <- quickSort(smaller) larger <- quickSort(larger) → There is no base case, so the function never stops calling itself and the recursion is infinite. It also calls quickSort on arrays that were never partitioned. Add a check for length <= 1 and partition before the calls.

return quickSort(smaller) + quickSort(larger) → The pivot is left out of the result, so it is lost from the sorted array. It should be quickSort(smaller) + [pivot] + quickSort(larger).

Section C: Definitions

quickSort(array) — A recursive function that picks a pivot, partitions the array into smaller and larger parts around it, then calls itself on each part until the array is sorted.

Section D: Fill in the Blanks

define quickSort(array)

if length(array) <= 1 then
    return array

pivot ← array[0]

for each item in rest
    if item < pivot then
        add item to smaller

left ← quickSort(smaller)
right ← quickSort(larger)
return left + [pivot] + right

Section E: Spot the Error

D — The loop should only go over the rest of the items. Looping over the whole array compares the pivot with itself and puts it in a part as well. It should be: for each x in rest.

A — The function header has no parameter, so the function has no array to sort and the pivot line cannot work. It should be: function quickSort(array).

A — Parameters in a function header must be separated by a comma. It should be: function split(array, pivot).

B — The base case must stop when the array has 0 or 1 items, so it uses <= 1. With >= 1 almost every array returns immediately and is never sorted. It should be: if length(array) <= 1 then.

B — The pivot must be a single element, not the whole array. It should be: pivot <- array[0].