I need some help with the Java Quick Sort and Merge Sort algorithms. Here are th
ID: 664111 • 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.
public class Sorts {
// do not make any changes to the header for this method
public static void quicksort(MyList<Integer> aList) {
// implement this method
}
// do not make any changes to the header for this method
public static void mergesort(MyList<Integer> aList) {
// implement this method
}
// add any other methods or variables you may wish
}
These classes are given - MyIterator, ArrayList, MyList:
public interface MyIterator<T> {
/**
Moves the iterator past the next element.
@return the traversed element
*/
T next();
/**
Tests if there is an element after the iterator
position.
@return true if there is an element after the iterator
position
*/
boolean hasNext();
}
import java.util.NoSuchElementException;
public class ArrayList<T extends Comparable<T>> implements MyList<T> {
int capacity = 16;
Object[] array = new Object[capacity];
int size = 0;
@Override
public void add(T item) {
if (size == capacity)
ensureCapacity(capacity * 2);
array[size] = item;
size++;
}
@Override
public int size() {
return size;
}
@SuppressWarnings("unchecked")
@Override
public T at(int index) {
if (index >= size)
throw new NoSuchElementException();
return (T)array[index];
}
@Override
public void setAt(int index, T item) {
if (index >= size)
throw new NoSuchElementException();
array[index] = item;
}
@Override
public void insertAt(int index, T item) {
if (index >= size)
throw new NoSuchElementException();
if (size == capacity)
ensureCapacity(capacity * 2);
for (int i = size - 1; i >= index; i--)
array[i + 1] = array[i];
array[index] = item;
size++;
}
@Override
public void removeAt(int index) {
if (index >= size)
throw new NoSuchElementException();
for (int i = index + 1; i < size; i++)
array[i - 1] = array[i];
size--;
}
@Override
public MyIterator<T> getIterator() {
return new ListIterator();
}
private class ListIterator implements MyIterator<T> {
int currentIndex = -1;
@SuppressWarnings("unchecked")
@Override
public T next() {
currentIndex++;
return (T)array[currentIndex];
}
@Override
public boolean hasNext() {
return currentIndex + 1 < size;
}
}
private void ensureCapacity(int minCapacity) {
if (minCapacity < size)
return;
int newCapacity = minCapacity < 16 ? 16 : minCapacity;
Object[] newArray = new Object[newCapacity];
System.arraycopy(array, 0, newArray, 0, size);
capacity = newCapacity;
array = newArray;
}
public void trimToSize() {
ensureCapacity(size);
}
}
public interface MyList<T extends Comparable<T>> {
/**
Adds an element at the end of the list.
*/
public void add(T item);
/**
Stores a new item at a specified index
Throws NoSuchElementException if index is out of bounds.
*/
public void setAt(int index, T item);
/**
Inserts an element at the specified index
Throws NoSuchElementException if index is out of bounds.
*/
public void insertAt(int index, T item);
/**
Removes the element at the specified index
Throws NoSuchElementException if index is out of bounds.
*/
public void removeAt(int index);
/**
Returns the element at the specified index
Throws NoSuchElementException if index is out of bounds.
*/
public T at(int index);
/**
Returns the size of the list.
@return the number of elements in the list
*/
public int size();
/**
Returns a list iterator for this list.
@return a list iterator for this list
*/
public MyIterator<T> getIterator();
}
Explanation / Answer
quick sort in java:
package com.java2novice.sorting;
public Class MyQuickSort {
private int MyArray[];
private int leng;
public void sortIt(int[], ipArr) {
if (ipArr == null || ipArr.length == 0 ) { return; }
this.array = ipArr;
leng = ipArr.length;
quickSort(0, leng - 1);
}
private void quickSort(int lowIndx, int HiIndx) {
int i = lowIndx;
int j = HiIndx;
int temp;
// let the middle index be the pivot chosen
int pivot = MyArray[lowIndx+(HiIndx-lowIndx)/2];
// split them into 2 arrays - those numbers less than the pivot goe to the left sub array and those greater than pivot // goes to the right sub array and the procedure gets repeated recursively
while (i <= j) {
while (MyArray[i] < pivot) { i++; }
while (MyArray[j] > pivot) { j--; }
if (i <= j) { temp = MyArray[i];
MyArray[i] = MyArray[j];
MyArray[j] = temp;
i++; j--;
}
}
// recursive call of quick sort function
if (lowIndx < j) quickSort(lowIndx, j);
if ( i < HiIndx) quickSort(i, HiIndx);
}
public static void main(String a[]) {
MyQuickSort sortIt = new MyQuickSort();
int [] input = {234,45,234,2,44,11,45,342,324,3,23};
sortIt.sort(input);
for(int i:input){
System.out.print(i);
System.out.print(" ");
}
}
}
************************ Merge Sort in Java *********************
package com.java2novice.sorting;
public class MergeSortMadeEasy {
private int[] array;
private int[] tempMergerArray;
private int leng;
public static void main(String a[]) {
int [] ipArr = { 32,565,12,354,5,33,456,22,45};
MergeSortMadeeasy msme = new MergeSortMadeEasy();
msme.sort(ipArr);
for (int i:ipArr){
System.out.print(i);
System.out.print(" ");
}
}
public coid sort(int ipArr[]) {
this.array = ipArr;
this.leng = ipArr.length;
this.tempMergerArray = new int[leng];
executeMergeSort(0, leng - 1);
}
private void executeMergeSort(int lowIndx, int HiIndx) {
if (lowIndx < HiIndx ) {
int mid = lowIndx + ( HiIndx - lowIndx) / 2;
// sort out the left portion of the array calling he same function recursively
executeMergeSort(lowIndx, mid);
// now the right portion
executeMergeSort(mid + 1, HiIndx);
// simply merge both portions
mergePortions(int lowIndx, int mid , int HiIndx) {
for (int i = lowIndx; i<=HiIndx; i++) tempMergerArray[i] = array[i];
int i = loxIndx;
int j = mid + 1;
int k = lowIndx;
while (i <= mid && j <= HiIndx) {
if (tempMergerArray[i] <= tempMergerArray[j]) {
array[k] = tempMergerArray[i]; i++;
} else { array[k] = tempMergerArray[j]; j++; }
k++;
}
while ( i <= mid ) {
array[k] = tempMergerArray[i]; k++; i++;
}
}
}
// ****** now the above two sort programs can be implemented into the headers given below: ******
public class Sorts {
// do not make any changes to the header for this method
public static void quicksort(MyList<Integer> aList) {
int i = lowIndx;
int j = HiIndx;
int temp;
// let the middle index be the pivot chosen
int pivot = MyArray[lowIndx+(HiIndx-lowIndx)/2];
// split them into 2 arrays - those numbers less than the pivot goe to the left sub array and those greater than pivot // goes to the right sub array and the procedure gets repeated recursively
while (i <= j) {
while (MyArray[i] < pivot) { i++; }
while (MyArray[j] > pivot) { j--; }
if (i <= j) { temp = MyArray[i];
MyArray[i] = MyArray[j];
MyArray[j] = temp;
i++; j--;
}
}
// recursive call of quick sort function
if (lowIndx < j) quickSort(lowIndx, j);
if ( i < HiIndx) quickSort(i, HiIndx);
}
}
// do not make any changes to the header for this method
public static void mergesort(MyList<Integer> aList) {
if (lowIndx < HiIndx ) {
int mid = lowIndx + ( HiIndx - lowIndx) / 2;
// sort out the left portion of the array calling he same function recursively
executeMergeSort(lowIndx, mid);
// now the right portion
executeMergeSort(mid + 1, HiIndx);
// simply merge both portions
mergePortions(int lowIndx, int mid , int HiIndx) {
for (int i = lowIndx; i<=HiIndx; i++) tempMergerArray[i] = array[i];
int i = loxIndx;
int j = mid + 1;
int k = lowIndx;
while (i <= mid && j <= HiIndx) {
if (tempMergerArray[i] <= tempMergerArray[j]) {
array[k] = tempMergerArray[i]; i++;
} else { array[k] = tempMergerArray[j]; j++; }
k++;
}
while ( i <= mid ) {
array[k] = tempMergerArray[i]; k++; i++;
}
}
}
}