Question

Java

(Determining Big O) write a PerformanceTest class and compare the performance of selection and bubblesort. Use the following “PerfomanceTest” example. Instead of a simple loop, use the mentioned sort algorithms.
⦁   Test with a sorted array
⦁   Test with an unsorted array (you can create the unsorted array randomly and then use the same one for both of the algorithms)

Answer 1

Program:

PerformanceTest.java:

//header files

import java.util.Random;

public class PerformanceTest {

// generate list of integers as static

static int[][] list = new int[2][];

static int[] list1 = new int[10];

static int[] list2 = new int[10];

// main function

public static void main(String[] args) {

// create a string of number say that holds the names of the sort

String algorithm[] = { "Selection Sort", "Bubble Sort"};

String size[] = { "10", "10"};

// call the display method to inform that which is hold which type of

// numbers

displayList();

// generate random numbers into the respective lists

generatelist();

// assign all the list's into the list of 2-D number say

list[0] = list1;

list[1] = list2;

//display the values in the list

for (int i = 0; i < list.length; i++)

{

System.out.println();

System.out.println("List size : " + size[i]);

for(int k=0;k<list[i].length;k++)

{

if(k%10==0)

System.out.println();

System.out.print(list[i][k]+" ");

}

System.out.println();

for (int j = 0; j < 2; j++) {

System.out.println("\nTrail : " + (j + 1));

System.out.print("The Elapsed time of " + algorithm[0]

+ " algorithm for " + size[i] + " items is = ");

SelectionSortTimingForAllList(list[i]);

System.out.print("The Elapsed time of " + algorithm[1]

+ " algorithm for " + size[i] + " items is = ");

BubbleSortTimingForAllList(list[i]);

}

}

}

// Method to generate the random numbers with in the given range

public static void generatelist()

{

list1 = generateRandomNumbers(10, 10);

list2 = generateSortedNumbers(10, 10);

}

// generateRandomNumbers method will generate the random numbers

// of the given range into the respective size of lists

public static int[] generateRandomNumbers(int length, int range) {

int[] randNums = new int[length];

Random rand = new Random();

for (int i = 0; i < length; ++i) {

randNums[i] = rand.nextInt(range);

}

return randNums;

}

// generateSortedNumbers method will generate the random numbers

// of the given range into the respective size of lists

public static int[] generateSortedNumbers(int length, int range) {

int[] randNums = new int[length];

Random rand = new Random();

for (int i = 0; i < length; ++i) {

randNums[i] = i+1;

}

return randNums;

}

// displayList will display the menu

public static void displayList()

{

System.out.println("1. List of 10 numbers.");

System.out.println("2. List of 10 numbers.");

}

// SelectionSortTimingForAllList method will contain a list to which

// selection sort method is called and the respective list run time is

// calculated

public static void SelectionSortTimingForAllList(int[] list)

{

StopWatch timer = new StopWatch();

timer.start();

selectionSort(list);

timer.stop();

System.out.println(timer.getElapsedTime() + " nanoseconds");

}

// BubbleSortTimingForAllList method will contain a list to which

// BubbleSort method is called and the respective list run time

// is calculated

public static void BubbleSortTimingForAllList(int[] list)

{

StopWatch timer = new StopWatch();

timer.start();

BubbleSort(list);

timer.stop();

System.out.println(timer.getElapsedTime() + " nanoseconds");

}

// Selection sort code

public static int[] selectionSort(int[] numbers) {

for (int i = 0; i < numbers.length - 1; ++i) {

int minIndex = i;

for (int j = i + 1; j < numbers.length; ++j) {

if (numbers[j] < numbers[minIndex])

minIndex = j;

}

swap(numbers, minIndex, i);

}

return numbers;

}

// Bubble Sort code

public static int[] BubbleSort(int[] numbers)

{

int size=numbers.length;

int k;

for (int i = size; i>=0; i--)

{

for (int j = 0 ;j < size-1; j++)

{

k = j+1;

if (numbers[j] < numbers[k])

{

swap(numbers, j, k);

}

else

{

break;

}

}

}

return numbers;

}

private static void swap(int[] numbers, int i, int j)

{

int temp = numbers[i];

numbers[i] = numbers[j];

numbers[j] = temp;

}

}

StopWatch.java:

import java.util.*;

import java.lang.*;

public class StopWatch

{

private long elapsedTime;

private long startTime;

private boolean isRunning;

// constructor that will sets the time to 0

public StopWatch()

{

reset();

}

// The start method will starts the stop watch and time starts accumulating

// now.

public void start()

{

if (isRunning)

return;

isRunning = true;

startTime = System.nanoTime();

}

// The stop method will stops the stop watch

// the stop time is added to the elapsed time

public void stop()

{

if (!isRunning)

return;

isRunning = false;

long endTime = System.nanoTime();

elapsedTime = elapsedTime + endTime - startTime;

}

// The getElapsedTime method return the elapsed time

public long getElapsedTime()

{

if (isRunning)

{

long endTime = System.nanoTime();

return elapsedTime + endTime - startTime;

}

else

return elapsedTime;

}

// The reset method will resets the elapsedTime to 0

public void reset()

{

elapsedTime = 0;

isRunning = false;

}

}

Sample Output: