This assignment will represent your final project You have studied chapters desc
ID: 3704290 • Letter: T
Question
This assignment will represent your final project
You have studied chapters describe five sorting algorithms – bubble sort, selection sort, insertion sort, merge sort and quicksort. Chapter 20 provides information, illustrations and example code on the merge sort and quicksort code. Chapter 19 provides information, illustrations and example code on the bubble sort , selection sort and insertions sort.
Your assignment for chapter 19 was to create software for either insertion sort or selection sort.
Your task for the Final Project is to conduct Bench Marking research to compare some of these algorithms you have studied in Computer Science I and II. You should design and implement 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 for that trial and report this result in your report. If a sorting algorithm takes too long for any 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.
Chapter 20 describes a way to 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. However, if you do not have the luxury of time, then the process described in chapter 20 will work fine.
You may separate the programs to test each sorting method into separate Netbeans Projects. One project per sorting algorithm. You can then run your varying data sets multiple times per project. Run each data set size 5 times per project and record the results. Alternately, you could incorporate each segment into a more comprehensive application. I would recommend making them individually first. If you have additional time, incorporate them into a single project. You may also consider working on this project collaboratively. if so, you can separate the task of creating different programs with a group member and then share components. If you work on the programs collaboratively. Each student must conduct their own test on the data sets and produce their own report and presentation.
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 a 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 the chart represents.Your report should summarize your findings
Finally, you must create and present a brief PowerPoint Presentation that outlines your research, findings and conclusions. The PowerPoint Presentation should not be more than 7 slides. I have a included a document describing the outline of a small research presentation.
Upload the following
Your Report as a Word Processing Document
Spreadsheet used to analyze you data and create the chart
The Code used to the Create Data for the Report in a Zipped Container File. This will be either 4 different projects or one comprehensive project in a zipped file container
PowerPoint Presentation
Explanation / Answer
ANSWER:
1)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.
2)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.
3)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.