CSC212 Homework 8 2014

--D. Thiebaut (talk) 20:30, 12 November 2014 (EST)

---

This homework assignment is due Nov. 21st, 2014, at 11:55 p.m.

Problem #1

• Write a program called Hw8_1.java based on the Quicksort program of Lab 12, that has the following properties:

• It receives an array A of ints (int[] A), along with two ints defining the low and high indexes it must apply itself.
• It receives an integer N, with N' less than or equal to the size of A.

        public static void Quicksort( int[] A,int low, int high, int N ) {
            ...
        }

• It partially sorts the array A so that the lowest N integers of the array end up sorted in the left-most side of the array, which contains index 0. For example, assume that the modified Quicksort receives A = [10, 3, 5, 1, 2, 9, 0, 3], and N = 3. Quicksort will stop as soon as the lowest 3 integers of A are located in the cells of A with lowest index, i.e. A = [0, 1, 2, 5, 10, 3, 9]. Note that only the lowest 3 integers are sorted, and less than all the other integers of A, which are left in the array A, unsorted.

• The purpose of this modified Quicksort is to have a very fast algorithm for locating the N lowest (or N highest) items of a large collection, without having to spend the time to sort the whole array.

Performance

• Your program has to be robust and avoid O(N²) complexity arrays
• Your program's execution time will be measured and compared to that of the solution program, on different arrays, some random, some sorted in increasing order, and others sorted in decreasing order. Your function will also be tested with values of N ranging from 0 to the length of A.
• The grade will be proportional to the speed of your program.

Submission

• Submit your program to Moodle, in the Homework 8, Problem 1 section.

Problem #2

TBA... Stay tuned...