NAME:

LOGIN:

PRECEPT:

COS 226 Exercises on Sorting


1. Which, if any, of the following programs from the textbook are stable: selection (Program 6.12), insertion (Program 6.13), or bubblesort (Program 6.14)?



















2. [Exercise 7.2, modified] Show how the file 1 0 0 1 1 1 0 0 0 0 0 1 0 1 0 0 is partitioned using Program 7.2.
















3. Given a list of N points, with integer x and y coordinates (say, 64-bits), describe an efficient algorithm to identify and remove all duplicates. Your algorithm should run in O(N log N) time in the worst case.