Using JAVA, we will look at the behavior of three different sorts on randomly ge

ID: 3593892 • Letter: U

Question

Using JAVA, we will look at the behavior of three different sorts on randomly generated lists of different sizes.

• The three sorts are bubblesort, insertion sort, and quicksort.

• Randomly generate integers in the range 0-99 for your random numbers. You may choose your own random number generation technique . You must document the source of your random number generation in the code.

Here is what your code should do:

1. Do this 10 times:

a. Generate a random list of 10 items

b. Have each algorithm sort the list.

c. Give the original list, the sorted list, and the number of comparisons done by each algorithm.

2. Do this 10 times:

a. Generate a random list of 100 items

b. Have each algorithm sort the list.

c. Give the original list, the sorted list, and the number of comparisons done by each algorithm.

3. Do this 10 times:

a. Generate a random list of 1000 items

b. Have each algorithm sort the list.

c. Give the original list, the sorted list, and the number of comparisons done by each algorithm.

4. At the end:

For each algorithm and each list length, give the average of the number of comparisons.

Explanation / Answer

import java.text.DecimalFormat;

import java.util.Arrays;

import java.util.Random;

public class Sorts {

static int SIZE;

static int[] values;

static void initValues() {

values = new int[SIZE];

Random rand = new Random();

for (int index = 0; index < SIZE; index++)

values[index] = rand.nextInt(SIZE+1); // range 0 t0 10000

}

static public void swap(int index1, int index2)

// Precondition: index1 and index2 are >= 0 and < SIZE.

// Swaps the integers at locations index1 and index2 of the values array.

{

int temp = values[index1];

values[index1] = values[index2];

values[index2] = temp;

}

static public void printValues()

// Prints all the values integers.

{

int value;

DecimalFormat fmt = new DecimalFormat("00");

System.out.println("The values array is:");

for (int index = 0; index < SIZE; index++) {

value = values[index];

if (((index + 1) % 10) == 0)

System.out.println(fmt.format(value));

else

System.out.print(fmt.format(value) + " ");

}

System.out.println();

}

// ///////////////////////////////////////////////////////////////

// Quick Sort

static int split(int first, int last) {

int splitVal = values[first];

int saveF = first;

boolean onCorrectSide;

first++;

do {

while (onCorrectSide)

// move first toward last

if (values[first] > splitVal)

else {

first++;

<= last);

}

<= last);

while (onCorrectSide)

// move last toward first

if (values[last] <= splitVal)

else {

last--;

<= last);

}

if (first < last) {

swap(first, last);

first++;

last--;

}

} while (first <= last);

swap(saveF, last);

return last;

}

static void quickSort(int first, int last) {

if (first < last) {

int splitPoint;

splitPoint = split(first, last);

// values[first]..values[splitPoint - 1] <= splitVal

// values[splitPoint] = splitVal

// values[splitPoint+1]..values[last] > splitVal

quickSort(first, splitPoint - 1);

quickSort(splitPoint + 1, last);

}

// bubble sort

static void bubbleSort(int arr[])

{

int n = arr.length;

for (int i = 0; i < n-1; i++)

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

if (arr[j] > arr[j+1])

{

// swap temp and arr[i]

int temp = arr[j];

arr[j] = arr[j+1];

arr[j+1] = temp;

}

static void insertionSort(int arr[])

{

int n = arr.length;

for (int i=1; i<n; ++i)

{

int key = arr[i];

int j = i-1;

/* Move elements of arr[0..i-1], that are

greater than key, to one position ahead

of their current position */

while (j>=0 && arr[j] > key)

{

arr[j+1] = arr[j];

j = j-1;

}

arr[j+1] = key;

}

// ///////////////////////////////////////////////////////////////

// Main

public static void main(String[] args) {

SIZE = 1;

int count = 1;

while(count <= 3){

SIZE = SIZE * 10;

initValues(); // filling array with random integer

// getting a copy of this

int original[] = Arrays.copyOf(values, SIZE);

long startTime = 0;

long endTIme = 0;

long total = 0;

System.out.println("FOR N = "+SIZE);

total = 0;

// calling Quick sort

System.out.println(" Quick Sort: ");

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

// copy original array value into values array

values = Arrays.copyOf(original, SIZE);

startTime = System.currentTimeMillis();

quickSort(0, SIZE-1);

endTIme = System.currentTimeMillis();

total = total + (endTIme-startTime);

}

System.out.println(" Average Time taken in 10 rounds of sorting on same data : " + total/10+" millis");

System.out.println();

total = 0;

// calling bubble sort

System.out.println(" Bubble Sort: ");

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

// copy original array value into values array

values = Arrays.copyOf(original, SIZE);

startTime = System.currentTimeMillis();

bubbleSort(values);

endTIme = System.currentTimeMillis();

total = total + (endTIme-startTime);

}

System.out.println(" Average Time taken in 10 rounds of sorting on same data : " + total/10+" millis");

System.out.println();

total = 0;

// calling Heap sort

System.out.println(" Insertion Sort: ");

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

// copy original array value into values array

values = Arrays.copyOf(original, SIZE);

startTime = System.currentTimeMillis();

insertionSort(values);

endTIme = System.currentTimeMillis();

total = total + (endTIme-startTime);

}

System.out.println(" Average Time taken in 10 rounds of sorting on same data : " + total/10+" millis");

System.out.println();

count++;

}

Sample run:

FOR N = 10

Quick Sort: