// Path: src/main/java/rogeriogentil/data/structures/chapter06/LinkedQueue.java
// public class LinkedQueue<E> implements Queue<E> {
// 
//    private SinglyLinkedList<E> list = new SinglyLinkedList<>();
// 
//    @Override
//    public void enqueue(E element) {
//       list.addLast(element);
//    }
// 
//    @Override
//    public E dequeue() {
//       return list.removeFist();
//    }
// 
//    @Override
//    public E first() {
//       return list.first();
//    }
// 
//    @Override
//    public int size() {
//       return list.getSize();
//    }
// 
//    @Override
//    public boolean isEmpty() {
//       return list.isEmpty();
//    }
// 
// }
// 
// Path: src/main/java/rogeriogentil/data/structures/chapter06/Queue.java
// public interface Queue<E> {
//    
//    /**
//     * Adds element e to the back of queue.
//     * @param e 
//     */
//    void enqueue(E element);
//    
//    /**
//     * Removes and returns the first element from the queue (or null if the queue is empty).
//     * @return E
//     */
//    E dequeue();
//    
//    /**
//     * Returns the first element of the queue, without removing it (or null if the queue is empty).
//     * @return The first element of the queue
//     */
//    E first();
//    
//    /**
//     * Returns the number of elements in the queue.
//     * @return 
//     */
//    int size();
//    
//    /**
//     * Returns a boolean indicating whether the queue is empty.
//     * @return {@code true} or {@code false}
//     */
//    boolean isEmpty();
// }


import java.util.Comparator;
import rogeriogentil.data.structures.chapter06.LinkedQueue;
import rogeriogentil.data.structures.chapter06.Queue;
package rogeriogentil.data.structures.chapter12;


/**
 *
 * @author Rogerio J. Gentil
 */
public class QuickSort {

    /**
     * Quick-sort contents of a queue.
     *
     * @param <K>
     * @param S
     * @param comp
     */
    public static <K> void quickSort(Queue<K> S, Comparator<K> comp) {
        int n = S.size();

        if (n < 2) {
            return;
        }

        // divide
        K pivot = S.first();            // using first as arbitrary pivot                

        Queue<K> L = new LinkedQueue<>();
        Queue<K> E = new LinkedQueue<>();
// Path: src/main/java/rogeriogentil/data/structures/chapter06/LinkedQueue.java
// public class LinkedQueue<E> implements Queue<E> {
// 
//    private SinglyLinkedList<E> list = new SinglyLinkedList<>();
// 
//    @Override
//    public void enqueue(E element) {
//       list.addLast(element);
//    }
// 
//    @Override
//    public E dequeue() {
//       return list.removeFist();
//    }
// 
//    @Override
//    public E first() {
//       return list.first();
//    }
// 
//    @Override
//    public int size() {
//       return list.getSize();
//    }
// 
//    @Override
//    public boolean isEmpty() {
//       return list.isEmpty();
//    }
// 
// }
// 
// Path: src/main/java/rogeriogentil/data/structures/chapter06/Queue.java
// public interface Queue<E> {
//    
//    /**
//     * Adds element e to the back of queue.
//     * @param e 
//     */
//    void enqueue(E element);
//    
//    /**
//     * Removes and returns the first element from the queue (or null if the queue is empty).
//     * @return E
//     */
//    E dequeue();
//    
//    /**
//     * Returns the first element of the queue, without removing it (or null if the queue is empty).
//     * @return The first element of the queue
//     */
//    E first();
//    
//    /**
//     * Returns the number of elements in the queue.
//     * @return 
//     */
//    int size();
//    
//    /**
//     * Returns a boolean indicating whether the queue is empty.
//     * @return {@code true} or {@code false}
//     */
//    boolean isEmpty();
// }


// Path: src/main/java/rogeriogentil/data/structures/chapter12/QuickSort.java
import java.util.Comparator;
import rogeriogentil.data.structures.chapter06.LinkedQueue;
import rogeriogentil.data.structures.chapter06.Queue;

package rogeriogentil.data.structures.chapter12;


/**
 *
 * @author Rogerio J. Gentil
 */
public class QuickSort {

    /**
     * Quick-sort contents of a queue.
     *
     * @param <K>
     * @param S
     * @param comp
     */
    public static <K> void quickSort(Queue<K> S, Comparator<K> comp) {
        int n = S.size();

        if (n < 2) {
            return;
        }

        // divide
        K pivot = S.first();            // using first as arbitrary pivot                

        Queue<K> L = new LinkedQueue<>();
        Queue<K> E = new LinkedQueue<>();
        Queue<K> G = new LinkedQueue<>();