NAME:

LOGIN:

PRECEPT:

COS 226 Exercises on Elementary Sorting


1. Which of the following programs from the textbook are stable: selection (Program 6.2), insertion (Program 6.3), bubblesort (Program 6.4), or shellsort (Program 6.5)?



















2. Suppose you are given a list of N points in the plane. Point i is described by two 16-bit integer coordinates x[i] and y[i]. Describe a sub-quadratic algorithm (better than N2, e.g, N4/3 or N log N) for printing out a list of all points that appear two or more times in the list.