Final Project- Comparison of Sorting Algorithms (NetBeans/ Java) This assignment
ID: 3764065 • 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
Bubble Sort
This is the simplest algorithm, however it’s the worst one in performance speaking. The average and worst case complexity are both O(n2). But there is good news, its complexity, for the best case, is only O(n). Here there is an animation that explains how it works: Bubble Sort Animation.
Merge Sort
The Merge Sort algorithm is better than Bubble Sort. The average and worst case complexity is O(nlogn). The best case (when the array is sorted) is also O(nlogn), but with some optimizations can be reduced to O(n). Here you can find another animation Merge Sort.
Quicksort
The Quicksort algorithm is usually faster than Merge Sort, despite they have the same average case complexity O(nlogn). However, the complexity for the worst case is O(n2), with some improvements it can be reduced. Here there is an animation: Quicksort.
Method A B
Selection 4950 4950
Bubble 99 9900
Insertion 99 5049
Merge 712 1028
Shell 413 649
Quick 543 1041
class Sorting
{
static int[] X = new int[100];
static int mergecount = 0;
static int quickcount = 0;
public static void selectionSort(int list[])
{
int count = 0;
int position = 0, n = list.length;
for(int j = 0; j < n-1; j++)
{
position = j;
for(int k = j+1; k < n; k++)
{
count++;
if(list[k] < list[position])
position = k;
}
Swap(list, j, position);
}
System.out.println("counter" + count);
}
public static void Swap(int list[], int j, int k)
{
int temp = list[j];
list[j] = list[k];
list[k] = temp;
}
public static void bubbleSort(int list[])
{
int count = 0;
boolean changed = false;
do
{
changed = false;
for(int j = 0; j < list.length - 1; j++)
{
count++;
if(list[j] > list[j + 1])
{
Swap(list, j, j+1);
changed = true;
}
}
} while(changed);
System.out.println("counter" + count);
}
public static void insertionSort(int list[])
{
int count = 0;
for(int p = 1; p < list.length; p++)
{
int temp = list[p];
int j = p;
count++;
for( ; j > 0 && temp < list[j - 1]; j = j-1)
{
list[j] = list[j - 1];
count++;
}
list[j] = temp;
}
System.out.println("counter" + count);
}
public static void mergeSort(int list[])
{
mergeSort(list, 0, list.length - 1);
System.out.println("counter" + mergecount);
}
public static void mergeSort(int list[], int first, int last)
{
if(first < last)
{
int mid = (first + last) / 2;
mergeSort(list, first, mid);
mergeSort(list, mid + 1, last);
Merge(list, first, mid, last);
}
}
public static void Merge(int list[], int first, int mid, int last)
{
int count = 0;
int first1 = first, last1 = mid;
int first2 = mid + 1, last2 = last;
int temp[] = new int[list.length];
int index = first1;
while(first1 <= last1 && first2 <= last2)
{
if(list[first1] < list[first2])
{
temp[index] = list[first1++];
mergecount++;
}
else
temp[index] = list[first2++];
index++;
mergecount++;
}
while(first1 <= last1)
temp[index++] = list[first1++];
while(first2 <= last2)
temp[index++] = list[first2++];
for(index = first; index <= last; index++)
list[index] = temp[index];
}
public static void shellSort(int list[])
{
int count = 0;
int n = list.length;
for(int gap = n / 2; gap > 0; gap = gap == 2 ? 1: (int) (gap/2.2))
for(int i = gap; i < n; i++)
{
int temp = list[i];
int j = i;
count++;
for( ; j >= gap && (temp < (list[j - gap])); j -= gap)
{
list[j] = list[j - gap];
count++;
}
list[j] = temp;
}
System.out.println("counter" + count);
}
public static void quickSort(int start, int finish, int list[])
{
int count = 0;
int left = start, right = finish, pivot, temp;
pivot = list[(start + finish) / 2];
do
{
while(list[left] < pivot)
{
left++;
quickcount++;
}
while(pivot < list[right])
{
right--;
quickcount++;
}
if(left <= right)
{
temp = list[left];
list[left++] = list[right];
list[right--] = temp;
quickcount++;
}
} while(left < right);
if(start < right)
quickSort(start, right, list);
if(left < finish)
quickSort(left, finish, list);
}
public static void copy(int list[])
{
for(int i = 0; i < list.length; i++)
X[i] = list[i];
}
public static void restore(int list[])
{
for(int i = 0; i < list.length; i++)
list[i] = X[i];
}
public static void displayArray(int list[])
{
for(int k = 0; k < list.length; k++)
System.out.print(list[k] + " ");
System.out.println();
}
public static void main(String args[])
{
int[] A = new int[100];
for(int i = 0; i < A.length; i++)
A[i] = i + 1;
int[] B = new int[100];
int q = 100;
for(int i = 0; i < B.length; i++)
B[i] = q--;
int[] C = new int[100];
for(int i = 0; i < C.length; i++)
C[i] = (int)(Math.random() * 100 + 1);
displayArray(A);
copy(A);
selectionSort(A);
displayArray(A);
restore(A);
}
static int compareCount = 0;
int compareInt(int a, int b)
{
compareCount++;
return a - b;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.