1. Add the Gnome Sort to the Bubble Sort and QuickSort program. See:

https://en.wikipedia.org/wiki/Gnome_sort

Count and display the number of comparisons needed for each of the sorts.

2. Run the sorts with data set sizes of 100, 200, 300, 400, and 500.

3. Create an Excel data sheet displaying the above values of n and for each n the following results:

a. Comparisons for the Gnome Sort

b. Comparisons for the Bubble Sort

c. Comparisons for the QuickSort

d. Value of n²

e. Value n x log₂n

4. Create an Excel line graph displaying the results. Should look something like (just the format, the values may be very different):

The Sorting Program:

package sorting;

import java.util.*;

import java.math.*;

/**

*

* @author mazurnm

*/

public class Sorting {

static int QuickCount = 0;

static int BubbleCount = 0;

static int GnomeCount = 0;

// print an array of integers, 10 elements per line

public static void print (int arr [])

{

int on_line; // number of elements printed on line

on_line = 0;

// Print each element in turn

for (int element : arr)

{

// need to go to a new line

if (on_line == 10)

{

System.out.println ();

on_line = 0;

}

System.out.print (element + " ");

on_line++;

}

}

// swap elements at indexes i1 and i2

public static void swap (int arr [], int i1, int i2)

{

int swapper;

swapper = arr [i1];

arr [i1] = arr [i2];

arr [i2] = swapper;

}

public static void BubbleSort (int arr [])

{

boolean swapped; // swapped is true, if values were swapped

int index; // current spot in the array

swapped = true;

// continue doing passes of the array until all

// elements are sorted

while (swapped)

{

swapped = false;

// do a pass of the algorithm

for (index = 0; index

{

// if out of order swap

BubbleCount++;

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

{

swap (arr, index, index + 1);

swapped = true;

}

}

}

}

public static void gnomeSort(int[] anArray)

{

int first = 1;

while (first

{

if (anArray[first - 1]

{

first ++;

}

else

{

int tmp = anArray[first - 1];

anArray[first - 1] = anArray[first];

anArray[first] = tmp;

if (-- first == 0)

{

first = 1;

}

}

}

}

// Quicksort that just generates low and high indexes

public static void QuickSort (int arr [])

{

QuickSortHelp (arr, 0, arr.length - 1);

}

// recursive QuickSort, low is starting index into the

// array section to be sorted, high is the ending index

// into the array to be sorted

public static void QuickSortHelp (int arr [], int low, int high)

{

int pivot; // value separating sets (first in array)

int lowMover, // index into first part of array

highMover; // index into last part of array

// if one element, already sorted, so only concerned

// with case of more than one element

if (low

{

pivot = arr [low];

lowMover = low + 1;

highMover = high;

// as long as the small number is on the correct

// side, keep moving to the right

QuickCount++;

while (lowMover

{

QuickCount++;

lowMover++;

}

// as long as large number is on the correct side

// keep moving to the left

QuickCount++;

while (highMover >= low && arr [highMover] > pivot)

{

QuickCount++;

highMover--;

}

// repeat the above process as long as there are

// values to swap

while (lowMover

{

swap (arr, lowMover, highMover);

// as long as the small number is on the correct

// side, keep moving to the right

lowMover++;

QuickCount++;

while (lowMover

{

QuickCount++;

lowMover++;

}

// as long as large number is on the correct side

// keep moving to the left

highMover--;

QuickCount++;

while (highMover >= low && arr [highMover] > pivot)

{

QuickCount++;

highMover--;

}

}

// move pivot to the middle

swap (arr, low, highMover);

// call recursively to sort the two "halves"

QuickSortHelp (arr, low, highMover - 1);

QuickSortHelp (arr, highMover + 1, high);

}

}

/**

* @param args the command line arguments

*/

public static void main(String[] args) {

int [] arr = new int [1000]; // array to be sorted

// initialize the array with random integers

for (int i = 0; i

arr [i] = (int) (Math.random () * 10000);

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

print (arr);

BubbleSort (arr);

System.out.println (" The sorted array after Bubble Sort is:");

print (arr);

// initialize the array with random integers

System.out.println (" ");

for (int i = 0; i

arr [i] = (int) (Math.random () * 10000);

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

print (arr);

QuickSort (arr);

System.out.println (" The sorted array after QuickSort is:");

print (arr);

System.out.println (" Bubble comparisons: " + BubbleCount);

System.out.println ("QuickSort comparisons: " + QuickCount);

System.out.println (" ");

}

}

*I added the gnome sort but I don't know what to do next.

Comparisons vs. Data Size 100000 90000 80000 70000 60000 50000 40000 30000 20000 10000 100 200 300 GnomeBubble-QuickSort-nxn x log2n Comparisons vs. Data Size 100000 90000 80000 70000 60000 50000 40000 30000 20000 10000 100 200 300 GnomeBubble-QuickSort-nxn x log2n