Question: You should design and implement Java programs to try to run at least f
ID: 3717107 • Letter: Q
Question
Question:
You should design and implement Java programs to try to run at least four of the five the sorting methods with random data sets of 10,000 20,000 100,000 200,000 1,000,000 and 2,000,000 items. You should run the program for each sorting algorithm 5 times for each data set size. Each time you run the program, you should record the time it takes to sort the data set and the size of the data. That is 5 readings for each data set size per sorting algorithm. If any sorting algorithm takes longer than 10 minutes to sort a particular data set size, you should stop the program. Create a timer, start the timer when the sort begins, stop the timer when the sort ends, and capture the value of the time that elapsed. Feel free to create your own way for recording the elapsed time.
P.S : You dont need to put in datasets if you dont want to. The main thing is the Java program for sorting in different methods with a timer on it.
Thanks
Explanation / Answer
Code:
import java.util.Random;
public class SortAlgorithmTime
{
// generate list of integers as static
static int[][] list = new int[6][];
static int[] list1 = new int[10000];
static int[] list2 = new int[20000];
static int[] list3 = new int[100000];
static int[] list4 = new int[200000];
static int[] list5 = new int[1000000];
static int[] list6 = new int[2000000];
// main function
public static void main(String[] args)
{
// create a string of array that holds the names of the sort
String algorithm[] = { "Bubble Sort", "Insertion Sort", "Merge Sort", "Selection Sort","Quick sort"};
String size[]={"10,000", "20,000", "100,000", "200,000", "1,000,000", "2,000,000" };
// call the display method to inform that which is hold which type of
// numbers
displayList();
// generate random numbers into the respective lists
generatelist();
list[0] = list1;
list[1] = list2;
list[2] = list3;
list[3] = list4;
list[4] = list5;
list[5] = list6;
for (int i = 0; i < list.length; i++)
{
System.out.println();
System.out.println("List size : "+size[i]);
System.out.println();
for (int j = 0; j < 5; j++)
{
System.out.println("Trail : "+ (j+1));
System.out.println();
System.out.print("The Elapsedtime of "+algorithm[0]+" algorthim for "+size[i]+" items is = ");
BubbleSortTimingForAllList(list[i]);
System.out.print("The Elapsedtime oof "+algorithm[1]+" algorthim for "+size[i]+" items is = ");
InsertionSortTimingForAllList(list[i]);
System.out.print("The Elapsedtime of "+algorithm[2]+" algorthim for "+size[i]+" items is = ");
MergeSortTimingForAllList(list[i]);
System.out.print("The Elapsedtime of "+algorithm[3]+" algorthim for "+size[i]+" items is = ");
SelectionSortTimingForAllList(list[i]);
}
}
}
// generatelist method will generate the random numbers with in the
// given range
public static void generatelist()
{
list1 = generateRandomNumbers(10000, 10000);
list2 = generateRandomNumbers(20000, 20000);
list3 = generateRandomNumbers(100000, 100000);
list4 = generateRandomNumbers(200000, 200000);
list5 = generateRandomNumbers(1000000, 1000000);
list6 = generateRandomNumbers(2000000, 2000000);
}
// displayList will display the menu
public static void displayList()
{
System.out.println("1. List of 10000 numbers.");
System.out.println("2. List of 20000 numbers.");
System.out.println("3. List of 100000 numbers.");
System.out.println("4. List of 200000 numbers.");
System.out.println("5. List of 1000000 numbers.");
System.out.println("6. List of 2000000 numbers.");
}
// quickSortTimingForAllList method will contain a list
// depending on the the quickSort method is called and the respective
// list run time is calculated
public static void quickSortTimingForAllList(int[] list)
{
StopWatch timer = new StopWatch();
timer.start();
quickSort(list);
timer.stop();
if(timer.getElapsedTime()==900000)
{
System.out.println("The Quick sort takes more than 15 minutes.");
System.out.println("The size of the data set is "+ list.length +".");
}
else
{
System.out.println(timer.getElapsedTime() + " milliseconds");
}
}
// MergeSortTimingForAllList method will contain a list
// depending on the the mergeSort method is called and the respective
// list run time is calculated
public static void MergeSortTimingForAllList(int[] list)
{
StopWatch timer = new StopWatch();
timer.start();
mergeSort(list);
timer.stop();
if(timer.getElapsedTime()==900000)
{
System.out.println("The Merge sort takes more than 15 minutes.");
System.out.println("The size of the data set is "+ list.length +".");
System.exit(0);
}
else
{
System.out.println(timer.getElapsedTime() + " milliseconds");
}
}
// BubbleSortTimingForAllList method will contain a list
// depending on the the 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();
if(timer.getElapsedTime()==900000)
{
System.out.println("The Bubble sort takes more than 15 minutes.");
System.out.println("The size of the data set is "+ list.length +".");
System.exit(0);
}
else
{
System.out.println(timer.getElapsedTime() + " milliseconds");
}
}
// SelectionSortTimingForAllList method will contain a list
// depending on the the selectionSort 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();
if(timer.getElapsedTime()==900000)
{
System.out.println("The Selection sort takes more than 15 minutes.");
System.out.println("The size of the data set is "+ list.length +".");
System.exit(0);
}
else
{
System.out.println(timer.getElapsedTime() + " milliseconds");
}
}
// InsertionSortTimingForAllList method will contain a list
// depending on the the insertionSort method is called and the respective
// list run time is calculated
public static void InsertionSortTimingForAllList(int[] list)
{
StopWatch timer = new StopWatch();
timer.start();
insertionSort(list);
timer.stop();
if(timer.getElapsedTime()==900000)
{
System.out.println("The Insertion sort takes more than 15 minutes.");
System.out.println("The size of the data set is "+ list.length +".");
System.exit(0);
}
else
{
System.out.println(timer.getElapsedTime() + " milliseconds");
}
}
// 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;
}
//Quick sort code
public static int[] quickSort(int[] numbers)
{
quickSortHelper(numbers, 0, numbers.length - 1);
return numbers;
}
private static void quickSortHelper(int[] numbers, int init, int last)
{
if ((last - init) < 1 || (last < 0))
{
return;
}
int pivotIndex = partitionList(numbers, init, last);
quickSortHelper(numbers, init, pivotIndex - 1);
quickSortHelper(numbers, pivotIndex + 1, last);
}
private static int partitionList(int[] numbers, int init, int last)
{
int lastAssignedPos = init;
for (int i = init; i < last; ++i)
{
if (numbers[i] < numbers[last])
{
swap(numbers, lastAssignedPos, i);
++lastAssignedPos;
}
}
swap(numbers, last, lastAssignedPos);
return lastAssignedPos;
}
//Merge Sort code
public static int[] mergeSort(int[] numbers)
{
return mergeSortHelper(numbers, 0, numbers.length - 1);
}
private static int[] mergeSortHelper(int[] numbers, int init, int last)
{
if ((last - init) == 0)
{
return new int[] { numbers[last] };
}
int mid = (last + init) / 2;
int[] subList1 = mergeSortHelper(numbers, init, mid);
int[] subList2 = mergeSortHelper(numbers, mid + 1, last);
return merge(subList1, subList2);
}
private static int[] merge(int[] subList1, int[] subList2)
{
int[] result = new int[subList1.length + subList2.length];
int sub1First = 0;
int sub2First = 0;
for (int i = 0; i < result.length; ++i)
{
if (sub1First == subList1.length)
{
result[i] = subList2[sub2First++];
} else if (sub2First == subList2.length)
{
result[i] = subList1[sub1First++];
} else if (subList1[sub1First]< = subList2[sub2First])
{
result[i] = subList1[sub1First++];
} else
{
result[i] = subList2[sub2First++];
}
}
return result;
}
//Bubble sort code
public static int[] bubbleSort(int[] numbers)
{
boolean swapped = false;
do
{
swapped = false;
for (int i = 0; i < (numbers.length - 1); ++i)
{
if (numbers[i] > numbers[i + 1])
{
swap(numbers, i, i + 1);
swapped = true;
}
}
} while (swapped);
return numbers;
}
//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;
}
//Insertion Sort code
public static int[] insertionSort(int[] numbers)
{
for (int i = 1; i < numbers.length; ++i)
{
for (int j = i; j > 0; --j)
{
if (numbers[j] < numbers[j - 1])
{
swap(numbers, j, j - 1);
} 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
//This class will keeps the trace of the time when a respective
//call has invoked. It contains start and stop methods
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.currentTimeMillis();
}
// 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.currentTimeMillis();
elapsedTime = elapsedTime + endTime - startTime;
}
// The getElapsedTime method return the elapsed time
public long getElapsedTime()
{
if (isRunning)
{
long endTime = System.currentTimeMillis();
return elapsedTime + endTime - startTime;
}
else
return elapsedTime;
}
// The reset method will resets the elapsedTime to 0
public void reset()
{
elapsedTime = 0;
isRunning = false;
}
}
Above one is Java code with 5 sorting method with timer
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.