Difference between revisions of "CSC212 Homework 8 2014"
(Created page with "--~~~~ ---- <br /> <bluebox> This homework assignment is due Nov. 21st, 2014, at 11:55 p.m. </bluebox> <br /> =Problem #1= <br />") |
(→Problem #1) |
||
| Line 8: | Line 8: | ||
=Problem #1= | =Problem #1= | ||
<br /> | <br /> | ||
| + | =Problem #1= | ||
| + | <br /> | ||
| + | * Write a program called Hw8_1.java based on the '''Quicksort''' program of [[CSC212 Lab 12 2014|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. | ||
| + | <br /> | ||
| + | <source lang="java"> | ||
| + | public static void Quicksort( int[] A,int low, int high, int N ) { | ||
| + | ... | ||
| + | } | ||
| + | </source> | ||
| + | <br /> | ||
| + | :* 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. | ||
| + | <br /> | ||
| + | ==Performance== | ||
| + | <br /> | ||
| + | * Your program has to be robust and avoid O(''N''<sup>2</sup>) complexity arrays | ||
| + | * Your program's execution time will be measured to that of the solution program, on different arrays, some random, some sorted in increasing order, and other in decreasing order. Your function will also be tested with values of ''N'' ranging from 0 to the length of A. | ||
Revision as of 21:53, 12 November 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
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(N2) complexity arrays
- Your program's execution time will be measured to that of the solution program, on different arrays, some random, some sorted in increasing order, and other in decreasing order. Your function will also be tested with values of N ranging from 0 to the length of A.
