public class BaseMerging { /** * Entry point for sample output. * * @param args the command line arguments */ public static void main(String[] args) { Queue q1 = new ListQueue(); q1.enqueue("T"); q1.enqueue("R"); q1.enqueue("O"); q1.enqueue("L"); q1.enqueue("E"); Queue q2 = new ListQueue(); q2.enqueue("X"); q2.enqueue("S"); q2.enqueue("P"); q2.enqueue("M"); q2.enqueue("E"); q2.enqueue("A"); System.out.println(q1.toString()); System.out.println(q2.toString());

//Q1 Queue merged = mergeQueues(q1, q2); System.out.println(merged.toString()); //Q2 String[] a = {"S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"}; sort(a); assert isSorted(a); show(a); //Q3 String[] b = {"S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"}; shuffle(b); show(b); shuffle(b); show(b); }

public class LinearNode{ private LinearNode next; private Item element; /** * Creates a node storing the specified element. * @param elem element to be stored */ public LinearNode(Item elem) { next = null; element = elem; }

/** * Returns the node that follows this one. * @return reference to next node */ public LinearNode getNext() { return next; } /** * Sets the node that follows this one. * @param node node to follow this one */ public void setNext(LinearNode node) { next = node; } /** * Returns the element stored in this node. * @return element stored at the node */ public Item getElement() { return element; } /** * Sets the element stored in this node. * @param elem element to be stored at this node */ public void setElement(Item elem) { element = elem; } }

public class ListQueue implements Queue, Comparable{ LinearNode tail; //back LinearNode head; //front private int count; private int modCount;

public ListQueue() { tail = null; count = 0; }

@Override public boolean isEmpty() { return count == 0; }

@Override public void enqueue(Item item) { LinearNode newNode = new LinearNode(item);

if(isEmpty()) head = newNode; else tail.setNext(newNode); tail = newNode; count++; modCount++; }

@Override public Item dequeue() { if(isEmpty()) throw new NoSuchElementException();

Item result = head.getElement(); head = head.getNext(); count--; modCount++; if(isEmpty()) tail = null;

return result; }

@Override public Item front() { if(isEmpty()) throw new NoSuchElementException();

return head.getElement(); } @Override public String toString() { LinearNode iter = head; String result = ""; while(iter != null) { result = iter.getElement() + " " + result; iter = iter.getNext(); } return result + "(front)"; }

@Override public int size() { return count; } @Override public int compareTo(Item i){ return ((Comparable)this.front()).compareTo(i); } @Override public Iterator iterator(){ return new LinkedListIterator(this); } /** * LinkedIterator represents an iterator for a linked list of linear nodes. */ private class LinkedListIterator implements Iterator { private final int iteratorModCount; // the number of elements in the collection private LinearNode current; // the current position /** * Sets up this iterator using the specified items. * * @param collection the collection the iterator will move over * @param size the integer size of the collection */ public LinkedListIterator(ListQueue o) { current = head; iteratorModCount = modCount; } /** * Returns true if this iterator has at least one more element * to deliver in the iteration. * * @return true if this iterator has at least one more element to deliver * in the iteration * @throws ConcurrentModificationException if the collection has changed * while the iterator is in use */ @Override public boolean hasNext() throws ConcurrentModificationException { if (iteratorModCount != modCount) throw new ConcurrentModificationException(); return (current != null); } /** * Returns the next element in the iteration. If there are no * more elements in this iteration, a NoSuchElementException is * thrown. * * @return the next element in the iteration * @throws NoSuchElementException if the iterator is empty */ @Override public Item next() throws ConcurrentModificationException { LinearNode previous = null; if (!hasNext()) throw new NoSuchElementException(); Item result = (Item)current.getElement(); previous = current; current = current.getNext(); return result; } }

}

Background In order to practice divide and conquer algorithms, we will apply the idea to sorting and other tasks. Your goal is to first create a method that uses the merge concept to integrate two queue ADTs. Second, you will re-implement mergesort from scratch to get a better understanding of its divide and conquer (D & C) nature. Lastly, you will create an O(nlogn) algorithm for shuffling an input array. Divide and Conquer algorithms are conceptually similar to the recursive programming technique we saw earlier in the course. The idea is to break apart a problem into multiple (large) pieces. For example, the half of an array, and then the second half of an array. In terms of recursion, we might save that the sub-problem is size n/2. This contrasts with tire standard n - 1 size of many recursive algorithms, where only a single piece of work is accomplished during each call. In general, D&C algorithms require multiple recursive calls while simple recursion, like summing or displaying a list, requires only a single call. D&C algorithms are often more complicated to write than simple recursive algorithms, but, the extra work pays off because D&C algorithms can end up with logarithmic Big-Oh factors instead of linear factors. This is why mergesort is an O(nlogn) algorithm. This document is separated into four sections: Background, Requirements, Testing, and Submission. You have almost finished reading the Background section already. In Requirements, we will discuss what is expected of you in this homework. In Testing, we give some basic suggestions on how the code may be tested. Lastly, Submission discusses how your source code should be submitted on BlackBoard. Requirements In this programming project you will practice the implementation of D&C algorithms. Download the attached base files for a starting place; they include some very simple testing code. You may modify the base file with your answers for all three questions. However, please retain the signatures of the two stub methods and make sure you keep all of your code in the base file. Also attached is Sorting java, which includes the textbook's sorting algorithm implementations for reference. The LinearNode, List Queue, and Queue classes should not be modified. (Sedgewick and Wayne: 2.2.14) Merging sorted queues. Develop a static- method that takes two queues of sorted items as arguments and returns a queue that results from merging the queues into sorted order. Emptying the input queues is fine. If you need to make any assumptions about the typing of the contents of the queues, please state them in a comment. Reimplement the mergesort algorithm to pass only arrays as parameters. This should include a helper method, public static Comparable|| mergesort(Comparable|| a), and a merge method, public static Comparable|| merge(Comparable|| a, Comparable|| b). Do not use global or class variables. (Note that this approach is slower than the mergesort from the book. The goal Is to better understand the mergesort concept.) Implement a method, public static void shuffle(Object|| a), that shuffles an array in nlog(n) time using a merging action. Assume calls to the Random library happen in constant time. It should be possible for any element to re-position to any other position. Include a comment explaining why your algorithm runs in nlogn time