import java.util.Random; public class CSE205_Assignment05 { public static Random rnd = new Random(); public static void main(String[] args) { System.out.println("Quicksort tests -----------------------------"); quicksort1_test(); quicksort10_test(); quicksort100_test(); System.out.println("Mergesort tests -----------------------------"); mergesort1_test(); mergesort10_test(); mergesort100_test(); } public static void quicksort1_test() { final int SIZE = 1; MyList l = new ArrayList(); for (int i = 0; i  l = new ArrayList(); for (int i = 0; i  l = new ArrayList(); for (int i = 0; i  l = new ArrayList(); for (int i = 0; i  l = new ArrayList(); for (int i = 0; i  l = new ArrayList(); for (int i = 0; i  aList) { for (int i = 0; i  aList) { for (int i = 1; i  
 
 
public interface MyIterator { /** 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(); }
 
 
 
public interface MyList> { /** 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 getIterator(); }
 
 
 
import java.util.NoSuchElementException; public class ArrayList> implements MyList { 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  getIterator() { return new ListIterator(); } private class ListIterator implements MyIterator { int currentIndex = -1; @SuppressWarnings("unchecked") @Override public T next() { currentIndex++; return (T)array[currentIndex]; } @Override public boolean hasNext() { return currentIndex + 1  
 
 
public class Sorts { // do not make any changes to the header for this method . . ----- public static void quicksort(MyList aList) { // implement this method } // do not make any changes to the header for this method . . ----- public static void mergesort(MyList aList) { // implement this method } // you may write and include any private methods you wish below . . ----- }
  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 MyList as an argument. Your algorithm must sort the list in ascending order. a a argument. Your algorithm must sort the list in ascending order. You may 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. 4.  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 MyList as an argument. Your algorithm must sort the list in ascending order. a a argument. Your algorithm must sort the list in ascending order. You may 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. 4