Sorting a Queue Using Recursion

Question

The question is this:

You need to sort a queue in a new member method void sort() you add to the queue.

The rules are:

You can not use any loops. Only recursion is allowed.
You can create as many private methods as you wish.
You may create and use two auxiliary queues of the same kind (call it Queue - has a default constructor).
You don't know anything about the internal structure of the queue.
The only methods given to you are: bool empty(), Data peek(), Data dequeue(), void enqueue(Data d)
dequeue() returns null if the list is empty, enqueue() ignores null inputs.
The sorting order needs to be ascending (front of queue should have the smallest value).
The comparable value is in integer inside the Data structure, called x.

I know it can be solved. I have yet to find an answer for this. Any ideas would be appreciated.

@userunknown Yes this is homework. What I have so far is an auxiliary method which takes a queue to sort, and splits it to 2 new queues, high and low, by each time taking 2 elements off the queue and putting them in the right auxiliary queue. This works well with even-length queues, but not with odd-length ones. — Yam Marcovic
– Yam Marcovic, Commented Jan 31, 2012 at 11:20
Well a) show us the code. b) What is the problem with odd-length queues? If this is your only problem - maybe you can add the last element twice, and remove one of them in the end? — user unknown
– user unknown, Commented Jan 31, 2012 at 11:47

Community · Accepted Answer · 2020-06-20 09:12:55Z

3

Start sorting a Queue of N=2 Elements.

Now - after solving this - improve the solution to sort N+1 Elements if N elements are sorted.

update:

Now, after you solved your homework, I can show an alternative solution in scala:

   private def insert (a: Int): Unit = {
     if (isEmpty || a <= peek) enqueue (a)
     else {
       val h = dequeue 
       insert (a)
       enqueue (h)
     }
   }
   
   def sort (): Unit = 
    if (! isEmpty) {
      val head = dequeue
      sort 
      insert (head)
    }

It works without an explicit second queue. The insert is a sortedInsert.

val q = new Queue (List (4))
q.enqueue (7)
q.enqueue (9)
q.enqueue (8)
q.enqueue (2)
q.enqueue (3)

val x = q.debug 
x: List[A] = List(3, 2, 8, 9, 7, 4)

q.sort 
val x = q.debug 
x: List[A] = List(2, 3, 4, 7, 8, 9)

I used a List to implement the Queue, but use it only for creating a new Queue and for debug reasons. Avoiding it would not be a big deal, but it was faster, and I wanted to start with the sorting. :)

edited Jun 20, 2020 at 9:12

CommunityBot

11 silver badge

answered Jan 31, 2012 at 10:21

user unknown

36.4k12 gold badges77 silver badges123 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Yam Marcovic Over a year ago

I believe there's a bug in your use of sorted insert. I think it has to do with peeking and then enqueuing where you should have "pushed". In other words I believe it doesn't work very well with a queue. The idea was very nice, though. If you care to try again and come up with a correct answer, I'll accept your answer.

Odobenus Rosmarus · Accepted Answer · 2012-01-31 10:32:33Z

2

look at merge sort. It was used for sorting data on tapes. I believe you can esily adopt it for queue.

answered Jan 31, 2012 at 10:32

Odobenus Rosmarus

6,0082 gold badges21 silver badges23 bronze badges

Comments

Yam Marcovic · Accepted Answer · 2012-01-31 13:07:58Z

First of all, thanks for the answers. They pointed me to the right solution. I voted them up to give credit, but since I managed to solve this question, I'll accept my own answer (at least until a better one comes).

So first of all, the homework was about "Taxies" (you know how homework is...) and a TaxiQueue, in Java.

The solution was:

public void sort() {
    sort(this);
}

private void sort(TaxiQueue toSort) {
    // Prepare split parts for later merging   
    TaxiQueue m1 = new TaxiQueue(), m2 = new TaxiQueue();

    // Return if there's only 1 element in the queue
    // since it's essentially "sorted".
    if(singleItem(toSort))
        return;

    // Split toSort into 2 parts
    split(toSort, m1, m2);
    // Sort each part recursively (by splitting and merging)
    sort(m1);
    sort(m2);
    // Merge each part into 1 sorted queue
    merge(toSort,  m1, m2);
}

private boolean singleItem(TaxiQueue tq) {
    Taxi temp = tq.dequeue();
    boolean retVal = tq.empty();
    tq.enqueue(temp);
    return retVal;
}

private void merge(TaxiQueue toSort, TaxiQueue m1, TaxiQueue m2) {
    // Notice that m1 and m2 are already sorted, and now we need
    // to merge them.
    // In the case that one of them is empty and the other one isn't,
    // simply append all remaining "higher" values into toSort.
    if(m1.empty()) {
        appendQueue(m2, toSort);
        return;
    }
    else if (m2.empty()) {
        appendQueue(m1, toSort);
        return;
    }
    // The critical comparison part...
    if(m1.peek().getId() < m2.peek().getId())
        toSort.enqueue(m1.dequeue());
    else
        toSort.enqueue(m2.dequeue());
    // Continue merging elements into toSort.
    merge(toSort, m1, m2);
}

// Split toSort into m1 and m2 as equally as possible
private void split(TaxiQueue toSort, TaxiQueue m1, TaxiQueue m2) {
    if(toSort.empty())
        return;
    m1.enqueue(toSort.dequeue());
    split(toSort,  m2, m1);
}

// Enqueue everything in src to dest.
private void appendQueue(TaxiQueue src, TaxiQueue dest) {
    if (src.empty())
        return;
    dest.enqueue(src.dequeue());
    appendQueue(src, dest);
}

I hope that other students may find it useful some day!

kamlesh nahata · Accepted Answer · 2012-01-31 16:00:04Z

0

@Yam Marcovic: Your answer is fine. Although you end up creating as many queues as there are elements in the original queue. May be that's something you would not like to do. Instead you could try a simpler approach where you would have to create only 2 new queues altogether ( call them originalQ, Q1, Q2 ).

Ill describe the recursive step.

Assume Q1 has n1 elements already sorted.
let new element from originalQ be s. If s can't be positioned correctly in Q by one enqueue operation then keep popping elements from Q1 ( compare them with s ) and put them correctly in Q2.
Now your Q2 is sorted with n1+1 elements, Q1 is empty. originalQ has one element less.Keep repeating the above steps.

answered Jan 31, 2012 at 16:00

kamlesh nahata

11 bronze badge

Comments

karthik3791 · Accepted Answer · 2014-08-07 16:29:18Z

The following method would aim to solve this problem using just one additional queue.

The algorithm uses Recursion to sort the queue.

Assume we have a function copy_from that can copy from one queue over to another queue as follows :-

  void copy_from (ArrayQueue&Q_from,ArrayQueue& Q_to){

       while(!Q_from.empty()){

       int t= Q_from.front();
       Q_to.enqueue(t);
       Q_from.dequeue();
     }
  }

The main sort function is as shown :-

void sort(ArrayQueue &Q, int element, ArrayQueue& Q2){

if(Q.size()==1){

    if(Q.front()>element){

         int front = Q.front();
         Q.dequeue();
         Q.enqueue(element);
         Q.enqueue(front);      
    }
    else{
        Q.enqueue(element);
    }

}
else{

 int front = Q.front();
 Q.dequeue();
 sort_v2(Q,front,Q2);

 int sorted_front = Q.front();
 if(element<sorted_front){

    Q2.enqueue(element);
    copy_from(Q,Q2);
    copy_from(Q2,Q);     

 }
 else{

      Q2.enqueue(sorted_front);
      Q.dequeue();
      //push into Q2 those elements which are smaller than element in Q.
      while(!Q.empty()&&Q.front()<element){
         Q2.enqueue(Q.front());
         Q.dequeue();
      }

      Q2.enqueue(element);
      copy_from(Q,Q2);
      copy_from(Q2,Q);

 }

}
}

When we initially call the sort function, we can call it as follows :-

 Queue Q, Q2; //Assume Q is the queue we want to sort and Q2 is an empty queue.
int front = Q.front();
Q.dequeue();
sort(Q,front,Q2);

Collectives™ on Stack Overflow

Sorting a Queue Using Recursion

5 Answers 5

update:

1 Comment

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

update:

1 Comment

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related