I\'m having a lot of trouble figuring out how to do this programming problem, pl
ID: 3687353 • Letter: I
Question
I'm having a lot of trouble figuring out how to do this programming problem, please help!
In this programming project you wl practice the implementation of sorting algorithms. Download the attached base file for a starting place; it includes some very simple testing code. You may modify the base file. However, please retain the signatures of the two stub methods and make sure you keep all of your code in the file. Also attached is Sorting java, which includes the textbook's sorting algorithm implementations for reference LC PP 9.4 modified]: Modify the quick sort method to choose the partition element using the middle- of-three technique described in the chapter 0 points Reimplement the mergesort algorithm to pass only arrays as parameters. This should include a helper method, public static Comparablell mer gesort(Comparablell a), and a merge method, public static Comparablel merge(Comparablell a, Comparablell b). Do not use global variables. (This approach is slower than the mergesort from the book. The goal is to better understand the mergesort concept.) 15 pointsExplanation / Answer
Solution: Please follow these algorithm as shown in below
(a)Quick sort with algorithm:
This method is also called partition exchange sort. This method is based on divide-and- conquer technique, i.e., the entire list is divided into various partitions and sorting is again and again applied on the partitions.
In this method, the list is divided into two, based on an element called the pivot element. Usually, the first element is considered to be the pivot element. Now, move the pivot ele- ment into its correct position in the list. The elements to the left of the pivot are less than the pivot while the elements to the right of the pivot are greater than the pivot. The process is repeated in each of these partitions. This process proceeds till we get the sorted list of elements. Let us understand this by an example. Consider the list-74, 39, 35, 32, 97, 84.
1.We will take 74 as the pivot and move it to a position so that the new list becomes 39, 35, 32, 74, 97, 84.
2.Now take the partitioned list 39, 35, 32. Let us take 39 as the pivot. Moving it to the correct position gives 35, 32, 39. Reapplying the process to the left partition 35, 32, we get 32, 35.
3.Apply the process to the right partition of 74. Taking 97 as the pivot and positioning it, we get 84, 97.
4.Assembling all the elements from each partition, we get the sorted list.
ALGORITHM FOR QUICK SORT:
1.Start.
2.Select the first element of the array as pivot.
3.Position the pivot such that the elements to the left of the pivot are less then the pivot and the elements to the right of the pivot are greater than the pivot.
4.Consider the left and right partition and repeat the steps 2 and 3.
5.Merge all the partitions to get the sorted list of elements.
6.Stop.
(b) Mersort Algorithm:
package com.javacodegeeks.sorting.utility;
import java.util.Comparator;
/*
* The utility class which contains static methods.
* */
public class SortingUtility
{
// order the array should be sort
public static final int ASC_ORDER = 1;
public static final int DESC_ORDER = 2;
/* class as a utility class that contains only static methods.
* creation of an object of this class
* constructor as private and also throwing an AssertionError to avoid
* creation of an object within the class.
* */
private SortingUtility()
{
throw new AssertionError();
}
public static<T extends Comparable<T>> void sort(T []a)
{
mergeSort(a,0, a.length-1, ASC_ORDER);
}
public static<T> void sort(T []a, Comparator<? super T>comparator)
{
mergeSort(a,0, a.length-1, ASC_ORDER,comparator);
}
public static<T extends Comparable<T>> void sort(T []a,int order)
{
mergeSort(a,0, a.length-1, order);
}
public static<T> void sort(T []a,int order, Comparator<? super T>comparator)
{
mergeSort(a,0, a.length-1, order,comparator);
}
public static<T extends Comparable<T>> void mergeSort(T []a,int lowerIndex,int upperIndex,int order)
{
if(lowerIndex == upperIndex)
{
return;
}else
{
int mid = (lowerIndex+upperIndex)/2;
mergeSort(a,lowerIndex,mid,order);
mergeSort(a,mid+1,upperIndex,order);
if(order == ASC_ORDER)
{
mergeAsc(a,lowerIndex,mid+1,upperIndex);
}else if(order == DESC_ORDER)
{
mergeDesc(a,lowerIndex,mid+1,upperIndex);
}else
{
throw new UnsupportedOperationException("The order you specified is not supported.");
}
}
}
public static<T> void mergeSort(T []a,int lowerIndex,int upperIndex,int order, Comparator<? super T>comparator)
{
if(lowerIndex == upperIndex)
{
return;
}else
{
int mid = (lowerIndex+upperIndex)/2;
mergeSort(a,lowerIndex,mid,order,comparator);
mergeSort(a,mid+1, upperIndex,order,comparator);
if(order == ASC_ORDER)
{
mergeAsc(a,lowerIndex,mid+1,upperIndex,comparator);
}else if(order == DESC_ORDER)
{
mergeDesc(a,lowerIndex,mid+1,upperIndex,comparator);
}else
{
throw new UnsupportedOperationException("The order you specified is not supported.");
}
}
}
public static<T extends Comparable<T>> void mergeAsc(T []a,int lowerIndexCursor,int higerIndex,int upperIndex)
{
Object []tempArray = getTempArray(a.length);
int tempIndex=0;
int lowerIndex = lowerIndexCursor;
int midIndex = higerIndex-1;
int totalItems = upperIndex-lowerIndex+1;
while(lowerIndex <= midIndex && higerIndex <= upperIndex)
{
if(((Comparable<T>)a[lowerIndex]).compareTo(a[higerIndex]) < 0)
{
tempArray[tempIndex++] = a[lowerIndex++];
}else
{
tempArray[tempIndex++] = a[higerIndex++];
}
}
while(lowerIndex <= midIndex)
{
tempArray[tempIndex++] = a[lowerIndex++];
}
while(higerIndex <= upperIndex)
{
tempArray[tempIndex++] = a[higerIndex++];
}
for(int i=0;i<totalItems;i++)
{
a[lowerIndexCursor+i] = (T) tempArray[i];
}
}
public static<T> void mergeAsc(T []a,int lowerIndexCursor,int higerIndex,int upperIndex,Comparator<? super T>comparator)
{
Object []tempArray = getTempArray(a.length);
int tempIndex=0;
int lowerIndex = lowerIndexCursor;
int midIndex = higerIndex-1;
int totalItems = upperIndex-lowerIndex+1;
while(lowerIndex <= midIndex && higerIndex <= upperIndex)
{
if(comparator.compare(a[lowerIndex],a[higerIndex]) < 0)
{
tempArray[tempIndex++] = a[lowerIndex++];
}else
{
tempArray[tempIndex++] = a[higerIndex++];
}
}
while(lowerIndex <= midIndex)
{
tempArray[tempIndex++] = a[lowerIndex++];
}
while(higerIndex <= upperIndex)
{
tempArray[tempIndex++] = a[higerIndex++];
}
for(int i=0;i<totalItems;i++)
{
a[lowerIndexCursor+i] = (T) tempArray[i];
}
}
public static<T extends Comparable<T>> void mergeDesc(T []a,int lowerIndexCursor,int higerIndex,int upperIndex)
{
Object []tempArray = getTempArray(a.length);
int tempIndex=0;
int lowerIndex = lowerIndexCursor;
int midIndex = higerIndex-1;
int totalItems = upperIndex-lowerIndex+1;
while(lowerIndex <= midIndex && higerIndex <= upperIndex)
{
if(((Comparable<T>)a[lowerIndex]).compareTo(a[higerIndex]) > 0)
{
tempArray[tempIndex++] = a[lowerIndex++];
}else
{
tempArray[tempIndex++] = a[higerIndex++];
}
}
while(lowerIndex <= midIndex){
tempArray[tempIndex++] = a[lowerIndex++];
}
while(higerIndex <= upperIndex){
tempArray[tempIndex++] = a[higerIndex++];
}
for(int i=0;i<totalItems;i++)
{
a[lowerIndexCursor+i] = (T) tempArray[i];
}
}
public static<T> void mergeDesc(T []a,int lowerIndexCursor,int higerIndex,int upperIndex,Comparator<? super T>comparator)
{
Object []tempArray = getTempArray(a.length);
int tempIndex=0;
int lowerIndex = lowerIndexCursor;
int midIndex = higerIndex-1;
int totalItems = upperIndex-lowerIndex+1;
while(lowerIndex <= midIndex && higerIndex <= upperIndex){
if(comparator.compare(a[lowerIndex],a[higerIndex]) > 0)
{
tempArray[tempIndex++] = a[lowerIndex++];
}
else
{
tempArray[tempIndex++] = a[higerIndex++];
}
}
while(lowerIndex <= midIndex)
{
tempArray[tempIndex++] = a[lowerIndex++];
}
while(higerIndex <= upperIndex){
tempArray[tempIndex++] = a[higerIndex++];
}
for(int i=0;i<totalItems;i++){
a[lowerIndexCursor+i] = (T) tempArray[i];
}
}
private static Object[] getTempArray(int length){
Object []tempArray = new Object[length];
return tempArray;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.