THIS IS FOR C PROGRAMMING. Using three sorts, Bubble Sort, Insertion Sort, and Q

ID: 3596484 • Letter: T

Question

THIS IS FOR C PROGRAMMING. Using three sorts, Bubble Sort, Insertion Sort, and Quicksort.

Randomly generate integers in the range 0-99 for your random numbers.

Do this 10 times:

Generate a random list of 10 items

Have each algorithm sort the list.

Give the original list, the sorted list, and the number of comparisons done by

each algorithm.

Do this 10 times:

Generate a random list of 100 items

Have each algorithm sort the list.

Give the original list, the sorted list, and the number of comparisons done by

each algorithm.

Do this 10 times:

Generate a random list of 1000 items

Have each algorithm sort the list.

Give the original list, the sorted list, and the number of comparisons done by

each algorithm.

At the end:

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

Explanation / Answer

Please find my implementation.

import java.text.DecimalFormat;

import java.util.Arrays;

import java.util.Random;

public class Sorts {

static int SIZE;

static int[] values;

static int comparisons = 0;

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){

comparisons++;

// move first toward last

if (values[first] > splitVal)

else {

first++;

<= last);

}

<= last);

while (onCorrectSide){

// move last toward first

comparisons++;

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++){

comparisons++;

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)

{

comparisons++;

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;

int comp = 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);

comp = comp + comparisons;

comparisons = 0;

}

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

System.out.println(" Average number of comparisions : " + comp/10);

System.out.println();

total = 0;

comp = 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);

comp = comp + comparisons;

endTIme = System.currentTimeMillis();

total = total + (endTIme-startTime);

comparisons = 0;

}

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

System.out.println(" Average number of comparisions : " + comp/10);

System.out.println();

total = 0;

comp = 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);

comp = comp + comparisons;

comparisons = 0;

}

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

System.out.println(" Average number of comparisions : " + comp/10);

System.out.println();

count++;

}

Sample run:

FOR N = 10

Quick Sort: