I have to create a queue in which you enter a number thing and it goes to it's correct place e.g. 35 goes after 36 but before 34. I want a reply in pseudocode, and here's what I've written. I decided to add the number to the end of the queue, and then insertion sort it. The parts with a @ at the start of the line HAVE to stay there and ARE correct:
@ adt QUEUE
@ //
@private int queue_rep[1...100];
@private int queue_top[1...100];
@//

@add (int X);
@proc
@ if queue_top <= 100
@then
@ queue_rep[queue_top] = X;
@ queue_top = queue_top + 1;
for j = 2 to length(q)
Do
Key = q[j]
i = j -1
while i>0 and q[i] > Key
Do
q[i+1] = q[i]
i=i-1
q[i+1] = Key

@ end if
@ end proc

@ end adt

thats some fucked up code. The for loop is not right, I don't see where the q, j, or i variables are defined, and where do the for and while loops end? What language is that supposed to be?

What's your question? I don't know the insertion sort algorithm off the top of my head (and I doubt anyone else does either), so you'd be better off comparing your code with a book than checking with us.

This is probably out of the scope of what you're doing, but a Priority Queue is the name of a queue that does precicely what you are describing, and PQs are generally (afaik) implemented using heaps, which is a better and more elegant data structure/algorithm than [insert item into array => insertion sort].

CodeRed, emphasis on *pseudocode*. But, you do have a point that the two loops don't seem to have an end. (Aside from that, your comments were just wrong.)

- taubz

Why do you want to insertion sort a normal queue...if you meant a priority queue (which I hope you do), then you should be using a Heap Sort. It is _much_ faster than the insertion sort ( O(log2(n) * n) versus O(n^2) ).