Part of my homework includes sorting a stack using a selection sort and I don't know how to do that.. We might have done it in class but I don't remember.
Basically I'm gonna have a stack of random integers called temp1 and then the integers are going to be going back and forth from temp1 to temp2 putting the largest one in the stack called ordered until all of them are sorted. This homework is very confusing I hope someone can help me
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
while (temp1 and temp2 are both not empty)
{
if (temp2 is empty)
{
move all elements from temp1 to temp2 except the
largest one
put largest value on ordered
}
else
{
move all elements from temp2 to temp1 except the
largest one
put largest value on ordered
}
print the three stacks with labels
}
Assume stacks t1, t2 and ord with t2 and ord empty.
Symbolize popping t1 top value and pushing it onto ord by: t1 -> ord.
Pseudo:
t1 -> ord
while t1 is not empty:
if( t1.top > ord.top )
ord -> t2
t1 -> ord
else
t1 -> t2
once t1 is empty, repeat procedure for t2
continue this cycle until both t1 and t2 are empty.
This seemed like an interesting exercise, so I did it. The above procedure works if there are no repeated values. even with repeated values (just tried it).
EDIT: I see why it works even with repeated values. It's because of the 1st step. A value is pushed onto ord each (half) cycle no matter what.
But top is private data so we don't have access to that from the application file so I'm assuming I have to somehow do it using only functions and I don't know how to do that...
Edit: I don't think that what our instructor said makes sense cause if you look at the while loop that he wants us to do it will never execute because we are putting all of the numbers in temp1 so temp2 will never have any values in it therefore the while loop will not execute
I guess I will have to write a do while loop but I still don't know how to sort the stack.