Part 1 - Correct Sorting Algorithms Create Java methods for each of the followin
ID: 3889909 • Letter: P
Question
Part 1 - Correct Sorting Algorithms Create Java methods for each of the following, based on sorting arrays of integers: 1. Bubble Sort 2. Selection Sort 3. Insertion Sort 4. Quick Sort 5. Merge Sort Part 2 - Time Trials for Sorting Algorithms Create a testing shell for a sorting method that that times the method. The testing shell should: • Generate a random array of integers of a prescribed length. • Start a timer. • Sort the array. • Stop the timer and calculate the elapsed time. You should test the five methods created for part 1 above, with increasing larger data sets 100, 1,000, 10,000, 100000, 1,000,000 and 10,000000 values First, determine which of the sizes is appropriate for each sorting method, based on the time it takes to sort. If a method takes more than one minute, then you do not need to test the method with that size data set. For example, a merge sort might work with 1,000,000 items in a few secondsbut a selection sort will take much longerso it might be okay to do the insertion sort up to 100000 items, but not with larger data sets. You can determine exactly which size data sets you use with each soring method - you have some flexibility, but the basic idea is not to run sorts that take more than about a minute or two to complete.Explanation / Answer
Solution:
Part-I
Bubble Sort:
void sortBubble(int array[], int a)
{
int m, n;
for ( int m = 0; m < a-1; m++)
// some values are already in place
for (n = 0; n < a-m-1; n++)
if (array[n] > array[n+1])
swapFunction(array[n], array[n+1]); // swap the values between two indexes of array
}
Selection Sort:
void sortSelection(int array[])
{
int x = array.length;
for (int m = 0; m < x-1; m++) //Move the boundaries of array which is unsorted
{
int min= m;
for (int n = m+1; n < x; n++)
if (array[n] < array[min]) // To find the minimum element in the array
min= n;
int t = array[min]; //To swap the minimum with the first element.
array[min] = array[i];
array[i] = t;
}
}
Insertion Sort:
void sortInsertion(int array[], int a)
{
int m, key, n;
for (m = 1; m < a; m++)
{
key = array[m];
n = m-1;
while (n >= 0 && arr[n] > key) // Move the items which are greater than the key to ahead of there position
{
array[n+1] = array[n];
n = n-1;
}
array[n+1] = key; // When the pass(comparing key with complete array) is finished then assign next element to the key
}
}
Quick Sort:
void sortQuick(int array[], int l, int h)
{
if (l < h)
{
int part= partition(array, l, h);
sortQuick(array, l, part-1);
sortQuick(array, part+1, high);
}
}
Merge Sort:
void sortMerge(int array[], int l, int r)
{
if (l < r)
{
int m = l+(r-l)/2;
sortMerge(array, l, m);
sortMerge(array, m+1, r);
merge(array, l, m, r);
}
}
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)