Description

Part1.

Create HW5_1.pdf file and write all your answers there

Problem 1. For a given array A = (2, 4, 6, 8, 0, 1, 3, 5) and a partition method below , show the

resulting array after making a call to Partition(A, 0, 7). Show each iteration step in detail.

Problem 2 . Trace the execution of test(4). Write it out.

void test(int n) {

if (n > 0) {

System.out.println(n);

test(n-1);

System.out.println(n);

}

}

Problem 3. Sorting question

Give an efficient algorithm to rearrange an array of n keys so that all the negative keys precede

all the nonnegative keys. Your algorithm must be in-place, meaning you cannot allocate

another array to temporarily hold the items. How fast is your algorithm?

Problem 4. It is often useful to have data already sorted to perform some operations. In the

questions below you need to explain whether an operation could be performed faster if the

values are sorted. Make sure to take the time spent to sorting into account. If yes, explain how

sorting helps performance in terms of running time. If not, describe a faster alternative

algorithm without sorting along with the runtime complexity.

1. Finding the average of a set of integers.

2. Computing the mode of a set of integers (e.g., the value that occurs most often).

3. Computing the median of a set of integers.

4. Checking whether an item at least as large as some specified value exists in the array.

5. Find the maximum value.

Problem 5: Use Bubble sort to sort numbers {5, 7, 1, 9, 45, 23, 7} in DECREASING order. Show

the resulting array after each step of the algorithm.

Part 2. Sort Detective

You will be given a program (download from TED) which is designed to measure

comparisons, data movements, and execution time for the six sorting algorithms

discussed in class and in your reading assignments:

•  Bubble sort
•  Check Sort
•  Insertion Sort
•  Selection Sort
•  Merge Sort
•  QuickSort

Slight problem: the buttons are not labeled properly. You must apply your understanding

of the general properties of the algorithms (and in some cases, of the code used to

implement them) to determine the proper labeling of the buttons.

Files for this assignment are provided:

•  hw5.jar
•  SortingAlgorithms.java

File To Submit

• HW5_2.txt

As you know from class, if you double the size of the input data that you give to a quadratic

the algorithm, it will do four times the work; by contrast, an O(NlogN) algorithm will do a bit more

then twice as much; and, a linear algorithm will do only twice as much work. As you also know,

the properties of the input data set can affect the expected performance of many of our sorting

algorithms. Before you begin the homework, you should review the expected performance of

the algorithms on various data sets.