Calculating a median and recording time using different sorting techniques

Definition: If a set of numbers is stored in a sorted array A of size n, we will consider the median to be the number A[n/2].

The program will use different methods to calculate the median of an array of numbers. Your program should be be written in Java. The strategies are as follows:

1. Sort the array A using Quicksort and return A[n/2]. ( use either the first or last item in the array as the pivot). NOTE: Do not pivot randomly

2. Use the Quickselect.

3. Use Selection to sort the array up to the n/2 position, then return A[n/2].

The goal of the project is to compare the running times of the different implementations, to see which one really is the fastest. Below are instructions for experiment:

[login to view URL] arrays of 100,000, 200,000, 300,000, 400,000 and 500,000 randomly-generated(use random generator) numbers between 1 and 1,000,000.

2. For each array:

a. Sort the array using Quicksort and return the n/2 item.

[login to view URL] Quickselect (reuse Quicksort’s partition method) to return the median.

c. Use Quickselect to pick the pivot in Quicksort, sort the array using Quicksort, and return the median.

d. Use the aborted selection sort and return the median.

3. Using a built-in timer in java, record the time each operation took starting after creation of the array and ending with the return of the median.

4. Run each method on each array 10 times, and keep track of the timer results.

5. Output of result: Below table must be filled with high-low times run.

Size Qucksort Enhanced Quicksort QuickSelect Selection Sort

100,000 ex-1230 ms

200,000

300,000

400,000

500,000

Java Algorithm Analysis

ID projekta: #25969801

Več o projektu