Java

Perform algorithm time measurement for all three quadratic sorting algorithms for Best Case (already sorted), Average Case (randomly generated), and Worst Case (inverse sorted) inputs. Use arrays sizes of 50K, 100K, and 200K to produce timing results.

I have already part of it. The selection sort is done. Need the bubble sort and the insertion sort.

import java.util.Random;

public class SortAnalysis {

private static Random rand = new Random();

public static void main(String[] args) {

final int INIT_SIZE = 50000;

final int EXP_SIZE = 10;

for (int size = INIT_SIZE; size <= 200000; size *= 2) {

long totalWorst = 0;

long totalAvg = 0;

long totalBest = 0;

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

//setup

int[] worstArray = populate(size, "DESC");

//start the clock

long start = System.currentTimeMillis();

//work

Sort.selectionSort(worstArray);

//stop the clock and measure time

totalWorst += System.currentTimeMillis() - start;

worstArray = null;

//setup

int[] avgArray = populate(size, " ");

//start the clock

start = System.currentTimeMillis();

//work

Sort.selectionSort(avgArray);

//stop the clock and measure time

totalAvg += System.currentTimeMillis() - start;

avgArray = null;

//setup

int[] bestArray = populate(size, "ASC");

//start the clock

start = System.currentTimeMillis();

//work

Sort.selectionSort(bestArray);

//stop the clock and measure time

totalBest += System.currentTimeMillis() - start;

bestArray = null;

}

System.out.printf("Experiment size: %,d ", size);

System.out.printf("Worst case: %,.3f ", totalWorst / 1000D / EXP_SIZE);

System.out.printf("Average case: %,.3f ", totalAvg / 1000D / EXP_SIZE);

System.out.printf("Best case: %,.3f ", totalBest / 1000D / EXP_SIZE);

}

}

public static int[] populate(int size, String method) {

int[] result = new int[size];

switch (method.trim().toUpperCase()) {

case "ASC":

for (int i = 0; i < size; i++)

result[i] = i;

break;

case "DESC":

for (int i = 0; i < size; i++)

result[i] = size - i - 1;

break;

default:

for (int i = 0; i < size; i++)

result[i] = rand.nextInt(10 * size);

}

return result;

}

}

Here is the sort file

public class Sort {

public static void bubbleSort(int[] array) {

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

for (int j = array.length - 1; j > i; j--)

if (array[j] < (array[j - 1]))

swap(array, j, j - 1);

}

public static void insertionSort(int[] array) {

for (int i = 1; i < array.length; i++) // Insert ith record

for (int j = i; (j > 0) && (array[j] < (array[j - 1])); j--)

swap(array, j, j - 1);

}

public static void selectionSort(int[] array) {

for (int i = 0; i < array.length - 1; i++) { // Select ith record

int lowindex = i; // Remember its index

for (int j = array.length - 1; j > i; j--) // Find the least value

if (array[j] < (array[lowindex]))

lowindex = j; // Put it in place

swap(array, i, lowindex);

}

}

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

int temp = array[i];

array[i] = array[j];

array[j] = temp;

}

}