Sorting an array with Stacks and Queues

Question

I need to create a method which sorts an array of integers using a Stack and a Queue. For instance if given [-1, 7, 0, 3, -2] -> [-2, -1, 0, 3, 7]. I'm completely lost at how to do this question, because I would just use a sorting method, however for this question I am not allowed to do that. Can anyone explain how to do this with a Stack and a Queue?

Answer 1

Many fast sorting algorithms (for example mergesort and quicksort) can be implemented efficiently on linked lists by using the fact that you can efficiently treat a singly-linked list as a stack (by prepending elements to the front) or queue (by appending elements to the back). Consequently, one possible way to solve this problem would be to take one of those sorting algorithms and approach it as if you were sorting a linked list rather than a normal sequence.

For example, here is one simple way that you could implement mergesort using queues. I've written this to sort Integers, but this could easily be extended to handle other types:

public void mergesort(Queue<Integer> sequence) {
    /* Base case: Any 0- or 1-element sequence is trivially sorted. */
    if (sequence.size() <= 1) return;

    /* Otherwise, split the sequence in half. */
    Queue<Integer> left  = new LinkedList<Integer>(),
                   right = new LinkedList<Integer>();
    while (!sequence.isEmpty()) {
        left.add(sequence.remove());
        if (!sequence.isEmpty()) {
           right.add(sequence.remove());
        }
    }

    /* Recursively sort both halves. */
    mergesort(left);
    mergesort(right);

    /* Merge them back together. */
    merge(left, right, sequence);
}

private void merge(Queue<Integer> one, Queue<Integer> two,
                   Queue<Integer> result) {
    /* Keep choosing the smaller element. */
    while (!one.isEmpty() && !two.isEmpty()) {
        if (one.peek() < two.peek()) {
            result.add(one.remove());
        } else {
            result.add(two.remove());
        }
    }

    /* Add all elements from the second queue to the result. */
    while (!one.isEmpty()) {
        result.add(one.remove());
    }
    while (!two.isEmpty()) {
        result.add(two.remove());
    }
}

Overall, this will run in O(n log n) time, which is asymptotically optimal.

Alternatively, you could use quicksort, as shown here:

public void quicksort(Queue<Integer> sequence) {
    /* Base case: Any 0- or 1-element sequence is trivially sorted. */
    if (sequence.size() <= 1) return;

    /* Choose the first element as the pivot (causes O(n^2) worst-case behavior,
     * but for now should work out fine.  Then, split the list into three groups,
     * one of elements smaller than the pivot, one of elements equal to the
     * pivot, and one of elements greater than the pivot.
     */
    Queue<Integer> pivot = new LinkedList<Integer>(),
                   less  = new LinkedList<Integer>(),
                   more  = new LinkedList<Integer>();

    /* Place the pivot into its list. */
    pivot.add(sequence.remove());

    /* Distribute elements into the queues. */
    while (!sequence.isEmpty()) {
        Integer elem = sequence.remove();
        if      (elem < pivot.peek()) less.add(elem);
        else if (elem > pivot.peek()) more.add(elem);
        else                          pivot.add(elem);
    }

    /* Sort the less and greater groups. */
    quicksort(less);
    quicksort(more);

    /* Combine everything back together by writing out the smaller
     * elements, then the equal elements, then the greater elements.
     */
    while (!less.isEmpty())  result.add(less.remove());
    while (!pivot.isEmpty()) result.add(pivot.remove());
    while (!more.isEmpty())  result.add(more.remove());
}

This runs in best-case O(n log n) time and worst-case O(n²) time. For an interesting exercise, try making it pick the pivot at random to get expected O(n log n) runtime. :-)

For an entirely different approach, you could consider doing a least-significant digit radix sort on the values, since you know that they're all integers:

public void radixSort(Queue<Integer> sequence) {
    /* Make queues for values with a 0 in the current position and values with a
     * 1 in the current position.  It's an optimization to put these out here;
     * they honestly could be declared inside the loop below.
     */
    Queue<Integer> zero = new LinkedList<Integer>(),
                   one  = new LinkedList<Integer>();

    /* We're going to need 32 rounds of this, since there are 32 bits in each
     * integer.
     */
    for (int i = 0; i < 32; i++) {
        /* Distribute all elements from the input queue into the zero and one
         * queue based on their bits.
         */
        while (!sequence.isEmpty()) {
            Integer curr = sequence.remove();

            /* Determine whether the current bit of the number is 0 or 1 and
             * place the element into the appropriate queue.
             */
            if ((curr >>> i) % 2 == 0) {
                zero.add(curr);
            } else {
                one.add(curr);
            }
        }

        /* Combine the elements from the queues back together.  As a quick
         * note - if this is the 31st bit, we want to put back the 1 elements
         * BEFORE the 0 elements, since the sign bit is reversed.
         */
        if (i == 31) {
            Queue<Integer> temp = zero;
            zero = one;
            one = temp;
        }
        while (!zero.isEmpty()) result.add(zero.remove());
        while (!one.isEmpty())  result.add(one.remove());
    }
}

This will run in time O(n log U), where U is the maximum possible value that can be stored in an int.

Of course, all of these algorithms are efficient and elegant. Sometimes, though, you will want to do a slow and inelegant sort like bogosort. Now, bogosort is somewhat difficult to implement, since it typically requires you to shuffle the input sequence, which is way easier to do on an array. However, we can simulate shuffling a queue as follows:

• Choose a random index into the queue.
• Cycle through that many elements.
• Remove that element from the queue and add it to the result.
• Repeat.

This ends up taking time O(n²) rather than O(n), which has the unfortunate side-effect of making bogosort take expected time O(n² &mdot; n!) rather than O(n &mdot; n!). However, it's the price we have to pay.

public void bogosort(Queue<Integer> sequence, Random r) {
    while (!isSorted(sequence)) {
        permute(sequence, r);
    }
}

/* Checking if a sequence is sorted is tricky because we have to destructively modify
 * the queue.  Our process will be to cycle the elements of the sequence making sure
 * that each element is greater than or equal to the previous element.
 *
 * Because we are using bogosort, it's totally fine for us to destructively modify
 * the queue as long as all elements that were in the original input queue end up
 * in the resulting queue.  We'll do this by cycling forward through the elements
 * and stopping if we find something mismatched.
 */
private void isSorted(Queue<Integer> sequence) {
    int last = Integer.MIN_VALUE;

    for (int i = 0; i < sequence.size(); i++) {
        int curr = sequence.remove();
        sequence.add(curr);

        if (curr < last) return false;
    }
    return true;
}

/* Randomly permutes the elements of the given queue. */
private void permute(Queue<Integer> sequence, Random r) {
    /* Buffer queue to hold the result. */
    Queue<Integer> result = new LinkedList<Integer>();

    /* Continuously pick a random element and add it. */
    while (!sequence.isEmpty()) {
        /* Choose a random index and cycle forward that many times. */
        int index = r.nextInt(sequence.size());
        for (int i = 0; i < index; i++) {
            sequence.add(sequence.remove());
        }
        /* Add the front element to the result. */
        result.add(sequence.remove());
    }

    /* Transfer the permutation back into the sequence. */
    while (!result.isEmpty()) sequence.add(result.remove());
}

Hope this helps!

Answer 2

You can implement a Selection sort fairly easily with a Stack and Queue:

If the data is originally on the stack, put it all on the Queue, and do the following:

int size = list.length; // list is the int[] sent as a method parameter.
while (size > 0) { // until we've placed all elements in their sorted positions
  int min = Integer.MAX_VALUE; // make sure the minimum is bigger than all the data
  for (int i = 0; i < size; i++) { // check all elements in the queue
    int temp = queue.dequeue(); // mark the current element
    if (temp < min) min = temp; // if it's a possible minimum record it.
    queue.enqueue(temp); // place it back in the queue so we don't lose data.
  }
  for (int i = 0; i < size; i++) { // go through and remove the minimum element
    int temp = queue.dequeue(); // mark the currently removed element
    if (temp == min) break; // if it's the minimum, stop we've removed it.
    queue.enqueue(temp); // otherwise put it back on.
  }
  stack.push(min); // put the minimum value on the stack (in sorted order)
  size--;  // we have one less element to consider, so decrement the size.
}

After the sort is over the elements will be sorted on the Stack, removing them all will return data in order Greatest to Least (which can easily be reversed).

No this is not very efficient, i'm assuming it's a homework assignment. Realisticaly if you want to sort data you should use Arrays.sort or Collections.sort which implement a merge sort for objects and a quicksort for primitives. These will be far faster (O(NlogN) vs O(N*N)). Realize however you'll need to have data in an array or a list to do this, not a stack or queue.