NAMES:

LOGINS:

PRECEPT:

COS 226 Exercises on Sorting 1

References: Lectures 4 and Section 3.1 in Algs4


1. Show, in the style of the trace on page 217, the result of using shellsort to sort the keys E A S Y T O S H E L L S O R T













2. Given an array of N points, with integer x and y coordinates (say, 64-bits), describe (on the back of this page) an efficient algorithm that to identify and remove all duplicates. Your algorithm can use a sort method, but should otherwise run in linear time. Give a crisp and concise English description of your algorithm - don't write Java code.