讲解CS 610、辅导Java编程语言、讲解cs/c++、辅导python设计

CS 610 Section 103 Fall 2018

PROGRAMMING ASSIGNMENT 1: SORTING

Prof. Baruch Schieber

Program:

Write a function COMPVEC(X, Y, `) that compares two vectors of integers of length `.

(Recall that for two such vectors X and Y of length `, X ? Y if and only if there exists

and index i ∈ {0, . . . , ` 1} such that X[j] = Y [j], for j = 0, . . . , i 1 and X[i] < Y [i].)

Implement the following three sorting algorithms on input that consists of n vectors of

integers of length ` using the function COMPVEC(X, Y, `) to perform all comparisons

between such vectors.

1. Mergesort,

2. Heapsort,

3. Quicksort.

Count the number of key comparisons by counting the calls to COMPVEC(X, Y, `).

Count the total running time by using the built-in clock function

The input instances:

1. Generate n = 100 randomly ordered vectors of integers between 0 and 99 of length ` = 5

2. Run each of the algorithms on the n generated vectors

3. Run each of the algorithms on the sorted vectors (output of previous step)

4. Run each of the algorithms on the reverse sorted vectors

5. Generate n = 210 = 1, 024 randomly ordered vectors of integers between 0 and 99 of

length ` = 3 and run each of the algorithms on the n generated vectors

6. Repeat the previous step for n = 215 = 32, 768 and 2

20 = 1, 048, 576

1 of 2

Analysis:

Tabulate the performance results, listing both the number of comparisons and the measured

clock times.

Use the tabulated number of comparisons on the random instances to determine (approximately)

the time complexity and the constant factor.

Do the running times correspond to the average-case time complexities?