Assignment Objectives After completing this assignment the student should be abl
ID: 3701270 • Letter: A
Question
Assignment Objectives After completing this assignment the student should be able to . Implement a Quicksort algorithm using recursion. Implement a Merge Sort algorithm using recursion Assignment Requirements For this assignment you are given the following Java source code files: CSE205_Assignment05.ava (This file is complete-you will make no changes to this file) MyList.java Mylterator.java ArrayList.java Sorts.java (This file is complete you will make no changes to this file) (This file is complete you will make no changes to this file) (This file is complete you will make no changes to this file) (you must complete this file) The specifications for these files are given below Special requirements Sorts 1. 2. You must implement a recursive Merge Sort algorithm that will take a MyListExplanation / Answer
// ------------ Sorts.java -----------
/*
* ------------- RESULT ---------------
* Quicksort tests -----------------------------
--- PASSED: quicksort1_test: allAscending
--- PASSED: quicksort10_test: allAscending
--- PASSED: quicksort100_test: allAscending
Mergesort tests -----------------------------
--- PASSED: mergesort1_test: allAscending
--- PASSED: mergesort10_test: allAscending
--- PASSED: mergesort100_test: allAscending
*/
public class Sorts {
// do not make any changes to the header for this method . . -----
public static void quicksort(MyList<Integer> aList) {
quickSortList(aList, 0, aList.size()-1);
}
// do not make any changes to the header for this method . . -----
public static void mergesort(MyList<Integer> aList) {
mergeSortList(aList, 0, aList.size() - 1);
}
private static void mergeSortList(MyList<Integer> aList, int l, int r)
{
if (l < r)
{
// Find the middle point
int m = (l+r)/2;
// Sort first and second halves
mergeSortList(aList, l, m);
mergeSortList(aList , m+1, r);
// Merge the sorted halves
merge(aList, l, m, r);
}
}
private static void merge(MyList<Integer> aList, int l, int m, int r)
{
// Find sizes of two lists to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp lists */
MyList<Integer> L = new ArrayList<Integer>();
MyList<Integer> R = new ArrayList<Integer>();
/* init list */
for(int i=0;i<n1;i++) {
L.add(0);
}
for(int i=0;i<n2;i++) {
R.add(0);
}
/*Copy data to temp lists*/
for (int i=0; i<n1; ++i)
L.setAt(i, aList.at(l + i));
for (int j=0; j<n2; ++j)
R.setAt(j,aList.at(m + 1+ j));
/* Merge the temp list */
// Initial indexes of first and second sublist
int i = 0, j = 0;
// Initial index of merged sublist array
int k = l;
while (i < n1 && j < n2) {
if (L.at(i) <= R.at(j)) {
aList.setAt(k, L.at(i));
i++;
}
else {
aList.setAt(k,R.at(j));
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1) {
aList.setAt(k,L.at(i));
i++;
k++;
}
/* Copy remaining elements of R[] if any */
while (j < n2)
{
aList.setAt(k, R.at(j));
j++;
k++;
}
}
private static void quickSortList(MyList<Integer> aList, int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition(aList, low, high);
// Recursively sort elements before
// partition and after partition
if(low < pi-1) {
quickSortList(aList, low, pi-1);
}
if(high > pi) {
quickSortList(aList, pi, high);
}
}
}
private static int partition(MyList<Integer> aList, int low, int high)
{
int pivot = aList.at(high);
int i = (low-1); // index of smaller element
for (int j=low; j<high; j++)
{
// If current element is smaller than or
// equal to pivot
if (aList.at(j) <= pivot)
{
i++;
// swap arr[i] and arr[j]
int temp = aList.at(i);
aList.setAt(i, aList.at(j));
aList.setAt(j, temp);
}
}
// swap arr[i+1] and arr[high] (or pivot)
int temp = aList.at(i+1);
aList.setAt(i+1, aList.at(high));
aList.setAt(high, temp);
return i+1;
}
private static int partition2(MyList<Integer> aList, int left, int right) {
int pivot = aList.at(left); // taking first element as pivot
while (left <= right) {
//searching number which is greater than pivot, bottom up
while (aList.at(left) < pivot) {
left++;
}
//searching number which is less than pivot, top down
while (aList.at(right) > pivot) {
right--;
} // swap the values
if (left <= right) {
int tmp = aList.at(left);
aList.setAt(left,aList.at(right));
aList.setAt(right, tmp);
//increment left index and decrement right index
left++;
right--;
}
} return left;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.