「CS61B」Note(7) Lab12 Merge and Quick Sort

/** Returns a queue of queues that each contain one item from items. */
private static <Item extends Comparable> Queue<Queue<Item>>
        makeSingleItemQueues(Queue<Item> items) {
    // Your code here!
    Queue<Queue<Item>> singleItemQueues = new Queue<Queue<Item>>();
    for (Item i : items) {
        Queue<Item> thisSingleItemQueue = new Queue<Item>();
        thisSingleItemQueue.enqueue(i);
        singleItemQueues.enqueue(thisSingleItemQueue);
    }
    return singleItemQueues;
}

/**
 * Returns a new queue that contains the items in q1 and q2 in sorted order.
 *
 * This method should take time linear in the total number of items in q1 and q2.  After
 * running this method, q1 and q2 will be empty, and all of their items will be in the
 * returned queue.
 *
 * @param   q1  A Queue in sorted order from least to greatest.
 * @param   q2  A Queue in sorted order from least to greatest.
 * @return      A Queue containing all of the q1 and q2 in sorted order, from least to
 *              greatest.
 *
 */
private static <Item extends Comparable> Queue<Item> mergeSortedQueues(
        Queue<Item> q1, Queue<Item> q2) {
    // Your code here!
    if (q1.isEmpty()) {
        return q2;
    }
    if (q2.isEmpty()) {
        return q1;
    }
    Queue<Item> result = new Queue<Item>();
    while (true) {
        if (q1.peek().compareTo(q2.peek()) < 0) {
            result.enqueue(q1.dequeue());
        } else {
            result.enqueue(q2.dequeue());
        }
        if (q1.isEmpty()) {
            for (Item i : q2) {
                result.enqueue(i);
            }
            break;
        }
        if (q2.isEmpty()) {
            for (Item j : q1) {
                result.enqueue(j);
            }
            break;
        }
    }
    return result;
}

public static <Item extends Comparable> Queue<Item> mergeSort(
        Queue<Item> items) {
    // Your code here!
    // Create a deep copy of items Queue to avoid changing the original one
    Queue<Item> itemsCopy = new Queue<Item>();
    for (Item j : items) {
        itemsCopy.enqueue(j);
    }
    if (itemsCopy.size() == 1 || itemsCopy.isEmpty()) { return itemsCopy; }
    if (itemsCopy.size() == 2) {
        Item item1 = itemsCopy.dequeue();
        if (item1.compareTo(itemsCopy.peek()) < 0) {
            Item item2 = itemsCopy.dequeue();
            itemsCopy.enqueue(item1);
            itemsCopy.enqueue(item2);
        } else {
            itemsCopy.enqueue(item1);
        }
        return itemsCopy;
    }
    Queue<Item> firstHalf = new Queue<Item>();
    int itemsSize = itemsCopy.size();
    for (int i = 0; i <= itemsSize / 2 - 1; i++) {
        firstHalf.enqueue(itemsCopy.dequeue());
    }
    return mergeSortedQueues(mergeSort(firstHalf), mergeSort(itemsCopy));
}

/**
 * Partitions the given unsorted queue by pivoting on the given item.
 *
 * @param unsorted  A Queue of unsorted items
 * @param pivot     The item to pivot on
 * @param less      An empty Queue. When the function completes, this queue will contain
 *                  all of the items in unsorted that are less than the given pivot.
 * @param equal     An empty Queue. When the function completes, this queue will contain
 *                  all of the items in unsorted that are equal to the given pivot.
 * @param greater   An empty Queue. When the function completes, this queue will contain
 *                  all of the items in unsorted that are greater than the given pivot.
 */
private static <Item extends Comparable> void partition(
        Queue<Item> unsorted, Item pivot,
        Queue<Item> less, Queue<Item> equal, Queue<Item> greater) {
    // Your code here!
    Queue<Item> unsortedCopy = new Queue<Item>();
    for (Item j : unsorted) {
        unsortedCopy.enqueue(j);
    }
    while(!unsortedCopy.isEmpty()) {
        if (unsortedCopy.peek().compareTo(pivot) == 0) {
            equal.enqueue(unsortedCopy.dequeue());
        } else if (unsortedCopy.peek().compareTo(pivot) < 0) {
            less.enqueue(unsortedCopy.dequeue());
        } else {
            greater.enqueue(unsortedCopy.dequeue());
        }
    }
}

/** Returns a Queue that contains the given items sorted from least to greatest. */
public static <Item extends Comparable> Queue<Item> quickSort(
        Queue<Item> items) {
    // Your code here!
    if (items.size() == 1 || items.isEmpty()) { return items; }
    if (items.size() == 2) {
        // Create a deep copy of items Queue to avoid changing the original one
        Queue<Item> itemsCopy = new Queue<Item>();
        for (Item j : items) {
            itemsCopy.enqueue(j);
        }
        Item item1 = itemsCopy.dequeue();
        if (item1.compareTo(itemsCopy.peek()) < 0) {
            Item item2 = itemsCopy.dequeue();
            itemsCopy.enqueue(item1);
            itemsCopy.enqueue(item2);
        } else {
            itemsCopy.enqueue(item1);
        }
        return itemsCopy;
    }
    Queue<Item> less = new Queue<>();
    Queue<Item> equal = new Queue<>();
    Queue<Item> greater = new Queue<>();
    partition(items, getRandomItem(items), less, equal, greater);
    return catenate(catenate(quickSort(less), equal), quickSort(greater));
}

Queue<Item> itemsCopy = new Queue<Item>();
for (Item j : items) {
    itemsCopy.enqueue(j);
}