NAMES:

LOGINS:

PRECEPTS:

COS 226 Exercises on Elementary Sorting

Reference: Section 2.1 in Algorithms 4/e


1. Show, in the style of the trace of Algorithm 2.1 on p. 249. the result of using selection sort to sort the keys: 

P I A Z Z A
Be sure to indicate the value of i and min after each iteration.













2. Show, in the style of the trace of Algorithm 2.2 on p. 251, the result of using insertion sort to sort the keys: 

P I A Z Z A

Be sure to indicate the value of i and j after each iteration.













3. Run the Graham scan algorithm to compute the convex hull of the following set of points: 

{ (6, 3), (5, 6), (8, 2), (2, 4), (3, 9), (1, 1), (1, 6) }
Use (1, 1) as the base point—it has the minimum y-coordinate. List the points that appear on the trial hull after each point is considered, in the order that they appear.

Warning: Be careful with (5, 6).