Final Project- Comparison of Sorting Algorithms (NetBeans/ Java) This assignment
ID: 3714130 • Letter: F
Question
Final Project- Comparison of Sorting Algorithms
(NetBeans/ Java)
This assignment will represent your final project
This chapter and previous chapters describe five sorting algorithms – bubble sort, selection sort, insertion sort, merge sort and quicksort. This chapter provides the merge sort and quicksort code. The previous chapters provide the bubble sort code and pseudocode for selection sort and insertions sort. Your assignment for the last chapter was to create software for either insertion sort or selection sort.
Your task here is to conduct benchmarking to compare the algorithms. You should 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, 10 times each. You should stop the program for the first trial of any sorting method that takes more than 15 minute to run and report this result. If a sorting algorithm takes too long for one trial, such as for 100,000 items, then it is not necessary to complete the trials for larger data sets, simply report the size of the data set for which that algorithm started to take too long.
You should submit a report with your results and conclusions about the experiment. Your report should describe how you conducted the experiment. Additionally, your report should include table containing data from an aspect of the overall research framework and data that you collected. Your report should also contain a chart that visually explains your interpretation of the results that chart represents.Finally your report should summarize your findings
Upload the following
Your Report as a Word Processing Document
Any Code used to Create Data for the Report in a Zipped Container File
PowerPoint Presentation
Explanation / Answer
class Sorting
{
void BubbleSort(int array[])
{
int n = array.length;
for (int i = 0; i < n-1; i++)
for (int j = 0; j < n-i-1; j++)
if (array[j] > array[j+1])
{
// swap temp and arr[i]
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
void InsertionSort(int array[])
{
int n = array.length;
for (int i=1; i<n; ++i)
{
int key = array[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 && array[j] > key)
{
array[j+1] = array[j];
j = j-1;
}
array[j+1] = key;
}
}
void SelectionSort(int array[])
{
for(int i=0; i<array.length-1; i++)
{
int temp,pos=i;
for(int j=i+1; j<array.length; j++)
if(array[j]<array[pos])
pos=j;
temp = array[i];
array[i] = array[pos];
array[pos] = temp;
}
}
void merge(int array[], int low, int middle, int high)
{
// Find sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */
int L[] = new int [n1];
int R[] = new int [n2];
/*Copy data to temp arrays*/
for (int i=0; i<n1; ++i) { L[i] = arr[l + i]; }
for (int j=0; j<n2; ++j) { R[j] = arr[m + 1+ j]; }
/* Merge the temp arrays */
int i = 0, j = 0; // Initial indexes of first and second subarrays
int k = l; // Initial index of merged subarry array
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of R[] if any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
void MergeSort(int array[], int low, int high)
{
// check if low is smaller than high, if not then the array is sorted
if (low < high) {
int middle = low + (high - low) / 2;
MergeSort(array, low, middle); // Sort the left side of the array
MergeSort(array, middle + 1, high); // Sort the right side of the array
merge(array, low, middle, high); // Combine them both
}
}
// Driver method
public static void main(String args[])
{
Random rand = new Random();
// Run each test 10 times
for (int i=0; i<10; ++i) {
int dataSize = 10000; // Change this variable for different datasets
int array[];
// fill array with random integers
for(int i=0; i<dataSize; i++) { array[i] = rand.nextInt(); }
long startTime = System.currentTimeMillis(); // start time
// change algorithm accordingly to test all
BubbleSort(array);
//SelectionSort(array);
//InsertionSort(array);
//MergeSort(array, 0, array.length-1);
long stopTime = System.currentTimeMillis(); // end time
long elapsedTime = stopTime - startTime; // running time
System.out.println(elapsedTime);
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.