I need some help with the Java Quick Sort and Merge Sort algorithms. Here are th
ID: 664041 • Letter: I
Question
I need some help with the Java Quick Sort and Merge Sort algorithms. Here are the requirements:
Needs to be a recursive Quicksort algorithm that will take a MyList as an argument, sorted in ascending order. Needs to be a recursive Merge Sort algorithm that will take a MyList as an argument, sorted in ascending order.
You can add any private static methods to the Sorts class that you wish to support your specific sort methods. You may not alter the headers (modifiers, return type, name, argument list) of the mergesort or quicksort methods. You must implement the bodies of these methods.
If you need the classes that were given for MyList just let me know. Thanks!
Explanation / Answer
public class Sorts
{
private List<Integer> quicksort(List<Integer> input){
if(input.size() <= 1){
return input;
}
int middle = (int) Math.ceil((double)input.size() / 2);
int pivot = input.get(middle);
List<Integer> less = new ArrayList<Integer>();
List<Integer> greater = new ArrayList<Integer>();
for (int i = 0; i < input.size(); i++) {
if(input.get(i) <= pivot){
if(i == middle){
continue;
}
less.add(input.get(i));
}
else{
greater.add(input.get(i));
}
}
return quickjoin(quicksort(less), pivot, quicksort(greater));
}
private List<Integer> quickjoin(List<Integer> less, int pivot, List<Integer> greater){
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < less.size(); i++) {
list.add(less.get(i));
}
list.add(pivot);
for (int i = 0; i < greater.size(); i++) {
list.add(greater.get(i));
}
return list;
}
public ArrayList<Integer> mergeSort(ArrayList<Integer> unsortedList)
{
if(unsortedList.size() <= 1)
{
return unsortedList;
}
ArrayList<Integer> sortedList = new ArrayList<Integer>();
ArrayList<Integer> left = new ArrayList<Integer>();
ArrayList<Integer> right = new ArrayList<Integer>();
int middle = unsortedList.size()/2;
//Splits the array into unsortedList size lists of size one
for(int i = 0; i < unsortedList.size(); i++)
{
if(i < middle)
{
left.add(unsortedList.get(i));
}
else
{
right.add(unsortedList.get(i));
}
}
left = mergeSort(left);
right = mergeSort(right);
//combines the lists
sortedList = merge(left, right);
return sortedList;
}
public ArrayList<Integer> merge(ArrayList<Integer> left, ArrayList<Integer> right)
{
ArrayList<Integer> mergedList = new ArrayList<Integer>();
while(left.size() > 0 || right.size() > 0)
{
if(left.size() > 0 && right.size() > 0)
{
if(left.get(0) < right.get(0))
{
mergedList.add(left.get(0));
left.remove(0);
}
else
{
mergedList.add(right.get(0));
right.remove(0);
}
}
else if(left.size() > 0)
{
mergedList.add(left.get(0));
left.remove(0);
}
else if(right.size() > 0)
{
mergedList.add(right.get(0));
right.remove(0);
}
}
return mergedList;
}
public void MergeTime(IOClass ioStream) throws IOException
{
ioStream.readFromFile();
ArrayList<Integer> sortedList = new ArrayList<Integer>();
long timeBefore = System.nanoTime();
sortedList = mergeSort(ioStream.getInputArray());
long timeAfter = System.nanoTime();
double rawTime = timeAfter - timeBefore;
double timeInMilli = rawTime/1000000;
if(isSorted(sortedList))
{
ioStream.setInputArray(sortedList);
System.out.print("MergeSort time (in Milli): ");
System.out.println(timeInMilli);
}
else
{
System.out.println("Not sorted!");
}
}
}