Write a Java program that uses Quick Sort and displays the execution time/runnin

Question

Write a Java program that uses Quick Sort and displays the execution time/running time in nanoseconds.

The pivot should be chosen in two different ways:

1) Pivot is the first number in the array

2) Pivot is the median of the first three numbers in the array

-Create an array of size 1000 that displays the input in three different ways:

(a) Ascending order

(b) Descending order

(c) Random order

This program should be able to compute the running time for each of the different ways of choosing the pivot in the three different orders stated above (ascending order, descending order, and random order).

Explanation / Answer

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.util.Random;
import java.util.Arrays;

public class Benchmarks extends JFrame
{
private static int numberOfRuns = 20;

private JTextField arraySizeInput, display;
private JComboBox chooseSortMethod;

private final long seed;
private int arraySize;

// Constructor
public Benchmarks()
{

super("Benchmarks");

Container c = getContentPane();
c.setLayout(new GridLayout(6, 1));

c.add(new JLabel(" Array size: "));
arraySizeInput = new JTextField(4);
arraySizeInput.setText("1000");
arraySizeInput.selectAll();
c.add(arraySizeInput);

chooseSortMethod = new JComboBox(sortMethodNames);
c.add(chooseSortMethod);

JButton run = new JButton("Run");
run.addActionListener(new RunButtonListener());
c.add(run);

c.add(new JLabel(" Avg Time (milliseconds): "));

display = new JTextField(" Ready");
display.setBackground(Color.YELLOW);
display.setEditable(false);
c.add(display);

// Use the same random number generator seed for all benchmarks
// in one run of this program:

seed = System.nanoTime();
}

// Fills a[] with random numbers and sorts it using the sorting method

// This is repeated numberOfRuns times for better accuracy
// Returns the total time it took in milliseconds.
private long runSort(double[] a, int sortMethod, int numberOfRuns)
{
long startTime;
long endTime;
long diffTime;
Random generator = new Random(seed);
for(int i= a.length-1; i>0; i--)
{
a[i]= generator.nextDouble();
}
startTime= System.nanoTime();
Quicksort quick = new Quicksort();
quick.sort(a);


endTime= System.nanoTime();
diffTime= endTime- startTime;

return diffTime ;
}

// Handles Run button events
private class RunButtonListener implements ActionListener
{
public void actionPerformed(ActionEvent e)
{
String inputStr = arraySizeInput.getText().trim();
try
{
arraySize = Integer.parseInt(inputStr);
}
catch (NumberFormatException ex)
{
display.setText(" Invalid array size");
arraySize = 0;
return;
}

if (arraySize <= 0)
{
display.setText(" Invalid array size");
return;
}

if (arraySize <= 0)
return;

int sortMethod = chooseSortMethod.getSelectedIndex() + 1;
double a[] = new double[arraySize];
double avgTime = (double)runSort(a, sortMethod, numberOfRuns)
/ numberOfRuns;
display.setText(String.format(" %.2f", avgTime));

arraySizeInput.selectAll();
arraySizeInput.requestFocus();
System.out.println("Array size = " + arraySize +
" Runs = " + numberOfRuns + " " +
sortMethodNames[sortMethod - 1] + " avg time: " + avgTime);

}
}

//************************************************************

public static void main(String[] args)
{
numberOfRuns = 20;
if (args.length > 0)
{
int n = -1;
try
{
n = Integer.parseInt(args[0].trim());
}
catch (NumberFormatException ex)
{
System.out.println("Invalid command-line parameter");
System.exit(1);
}
if (n > 0)
numberOfRuns = n;
}

Benchmarks window = new Benchmarks();
window.setBounds(300, 300, 180, 200);
window.setDefaultCloseOperation(EXIT_ON_CLOSE);
window.setVisible(true);
}
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.