TR Forums

Asin · Thu Jun 17, 2004 4:03 pm

I recently completed this assignment and there was this one bonus question that has been bugging me ever since.

Here's the problem (in Java, really doesn't matter): there is a queue of int wrapper objects (Integer class) in which no two objects have the same int value stored. The queue is passed to a method and the question asks to sort the entire queue using no helper variables whatsoever. Keeping in mind that a for loop requires a counter variable in order to iterate.

For proof that I am not looking for an answer to this assignment and for clarity of the question, you can find it here (it's Question #2).

The QueueInterface interface contains the following method definitions:
public void createQueue ();
public boolean isEmpty ();
public void dequeueAll ();
public void enqueue (Object newItem);
public Object dequeue ();
public Object peek ();

I am looking for a solution to the +2 bonus, using no helper variables whatsoever. I was able to sort the queue using only one of the two helper stacks for a +1 though.

Thanks.

Fri Jun 18, 2004 8:24 pm

Here is a chunk of pseudo code that would solve the problem. For this to work, it would have to be implemented in a language that passes function parameters by value (ex: C++, Java) and hence makes a copy of the parameter that can be modified without changing the original.

Queue sortAscending(Queue q) {
  q.enqueue(q.peek());  //Store our marker to exit loop
  q.enqueue(q.peek());
  while(1) {
    //now cycle through the queue until we reach our end of queue
    //marker
    while(returnSecond(q).intValue() != q.peek().intValue()) {
      //compare the head of the queue to the second object in the queue
      if(q.peek().intValue() < returnSecond(q).intValue()) {
        //if the first is smaller, the put it at the back of the queue
        q.enqueue(q.dequeue());
      } else {
        //if the second is smaller, put the second at the back of the queue
        q.enqueue(returnSecond(q));
        //now put the first at the back of the queue
        q.enqueue(q.dequeue());
        //we can dump this object since we already put it at the back of 
        //the queue two statements prior
        q.dequeue();
      }
    }
    //at this point, we have processed our entire queue, exchanging out
    //of order pairs as we went
    //Move our end of queue marker back to the end
    q.enqueue(q.dequeue()); 
    q.enqueue(q.dequeue());
    //now we step through the entire queue and check to see if there are
    //any pairs that are out of order
    while(q.peek().intValue() < returnSecond(q).intValue() || getSecond(q).intValue() != q.peek().intValue()) {
      q.enqueue(q.dequeue());
    }
    //we finished our loop, so lets figure out how we exited.  If the first two 
    //items in the queue are deplicates, then we processed the entire queue
    //and found no out of order pairs.  When can exit our sort loop now.
    if (returnSecond(q).intValue() == q.peek().intValue()) {
      break;
    }
    //otherwise, we exited because we found an out of order pair.  Now we 
    //need to finish rotating through our queue to prep it for another sort
    //pass, so keep looking for the duplicate pair.
    while( returnSecond(q).intValue() != q.peek().intValue()) {
       q.enqueue(q.dequeue());
    }
    //Move our end of queue marker back to the end of the queue
    q.enqueue(q.dequeue());
    q.enqueue(q.dequeue());
  }
  //we now have a queue sorted in ascending order. 
  //remove the end of queue markers and return the queue.
  q.dequeue();
  q.dequeue();
  return(q);
}


Object returnSecond (Queue q) {
  //Throw away the first item in the queue.  We don't care about it.
  q.dequeue();
  //Return the next item in the queue.
  return(q.peek());
}

Edited to fix code formatting

--SS

sativa · Fri Jun 18, 2004 9:09 pm

uh oh a while(1) loop.

thats automatic points off

Sat Jun 19, 2004 9:35 am

sativa wrote:
uh oh a while(1) loop.

thats automatic points off

At least it's not...

label:
  ...
  do stuff
  ...
  goto label

--SS

IntelMole · Sat Jun 19, 2004 2:02 pm

</pointless squabbling until after the problem has been sorted?>

:-P

,
-Mole

Asin · Sat Jun 19, 2004 4:25 pm

See here's the thing though. Everytime that you make a call to returnSecond, the object at the front of the queue is destroyed and the Java garbage collector picks it up because you're not storing the object at the front.

In Java (and possibly C++), any objects that are passed as arguments are passed by reference. So any changes made to variable 'q' will be permanent.

If there was a while to take a look at the second object in the queue, then we would have nothing less of a simply bubble sort. But we can't see the second object without destroying the first.

sativa · Sat Jun 19, 2004 6:27 pm

Asin wrote:
In Java (and possibly C++), any objects that are passed as arguments are passed by reference. So any changes made to variable 'q' will be permanent.

Normal variables in C++ are not automatically passed by reference. Its different if your dealing pointers though.

its worth noting that in such a situation (the non-pointer one) the C++ compiler will simply allocate new memory space for your variable in the routine. That is no different from passing it by reference & storing its value in a second variable. So once your routine has gone out of scope C++ simply marks the memory space as free again.

My point is: the same thing ends up happening either way.

Asin · Sat Jun 19, 2004 7:14 pm

It's been a long time since I've dealt with C++. Even then I was still only barely scraping the surface of C++ as I was a high school student back then.

I do remember however that you have to explicitly say whether a variable is passed by value or by reference in C++.

But I just wanted to make it clear that in Java, there is no need to explicitly say this. All objects (arrays, and class instances) will be passed by reference to a method unless somewhere in side that method you redeclare that array or object with the "new" keyword.

So in fact, the signature for this queue sorting thing is:
public void sortQueue (QueueInterface q);

There is no need to return anything.

QueueInterface aQueue = new Queue ( ... );
// add stuff to the queue
sortQueue (aQueue); // QueueInterface newQueue = sortQueue (aQueue); is not needed.
// qQueue is now sorted.

Sun Jun 20, 2004 12:23 pm

Java handles all variable by reference except when passing them as arguements, in which case it passes by value. Of course I'm not a Jave programmer, I'm just stating what a web search turned up. Here are the first two hits for a google search on "java pass by value".

http://www.javaworld.com/javaworld/javaqa/2000-05/03-qa-0526-pass.html
http://javadude.com/articles/passbyvalue.htm

I'm pretty certain that the problem as stated cannot be solved without using a function call to implicitly make a new temporary variable. Of course, I have been wrong before.

--SS

Yahoolian · Mon Jun 21, 2004 11:40 am

What if

Object returnSecond (Queue q) {
  //Throw away the first item in the queue.  We don't care about it.
  q.dequeue();
  //Return the next item in the queue.
  return(q.peek());
}

was modified to be

Object returnSecond (Queue q) {
  //Throw away the first item in the queue.  We don't care about it.
  q.enqueue(q.dequeue());
  //Return the next item in the queue.
  return(q.peek());
}

But that sort of screws up the way that you did it.

Asin · Mon Jun 21, 2004 2:15 pm

That might screw a few things up.

Like the boolean expression in the first nested while loop will need to be switched to

q.peek ().intValue () != returnSecond (q).intValue ()

And I think that it might screw up the second nested while loop too.

TR Forums

Sorting a queue.

Sorting a queue.

Who is online