Sorting not working properly

Question

I am trying to figure out why this works, but when I can the numbers around it doesn't. What the code is suppose to do is have two stacks, the program is suppose to sort in ascending order, which it does, but if I change the:

first.Push(7)

to something like

first.Push(80)

it doesn't work. Can someone explain this, please? Here is what I have:

using System;
using System.Collections;

namespace Project03_03
{
   class Program
   {
      static void Main(string[] args)
      {
          Stack first = new Stack();
          first.Push(50);
          first.Push(45);
          first.Push(11);
          first.Push(7);

          Stack second = new Stack();
          second.Push(67);
          second.Push(65);
          second.Push(32);
          second.Push(12);

          ProcessInOrder(first, second);

          Console.WriteLine(
              "Press any key to continue...");
          Console.ReadKey();
      }

      static void ProcessInOrder(Stack first,
          Stack second)
      {
          while (first.Count > 0 || second.Count > 0)
          {
              if (first.Count == 0)
              {
                  Console.WriteLine(second.Pop());
                  continue;
              }

              if (second.Count == 0)
              {
                  Console.WriteLine(first.Pop());
                  continue;
              }

              if ((int)first.Peek()
                  >= (int)second.Peek())
              {
                  Console.WriteLine(
                      second.Pop());
              }
              else
              {
                  Console.WriteLine(first.Pop());
              }
          }

      }
  }
}

Please could you provide some output to define both your expected and actual results? — Evil Dog Pie, Mar 23 '15 at 14:13
It's the difference between your stacks being sorted and not sorted. — juharr, Mar 23 '15 at 14:13
Your code will only output all values in ascending order **if the stacks themselves are already in ascending order** If you do `first.Push(80)` instead of `first.Push(7)`, first is no longer in ascending order. — Dennis_E, Mar 23 '15 at 14:13
While first.Count is larger than 0 and then you check if first.Count is 0? Excuse me but what? — Thomas Lindvall, Mar 23 '15 at 14:14
*If* the stacks were sorted to begin with, then what you are doing is similar to the merge part of a mergesort. But they *are not* sorted, so this fails. — crashmstr, Mar 23 '15 at 14:14
As an aside, there's no reason to use the non-generic [`Stack`](https://msdn.microsoft.com/en-us/library/system.collections.stack%28v=vs.110%29.aspx) anymore since there is a generic [`Stack`](https://msdn.microsoft.com/en-us/library/3278tedw(v=vs.110).aspx), the same applies to `Queue`+`Queue` or `ArrayList` + `List`. — Tim Schmelter, Mar 23 '15 at 14:14
@ThomasLindvall the `while` has an OR, so either stack could be empty inside the loop. That's why the OP then pops from the other stack. — juharr, Mar 23 '15 at 14:15
@juharr yea but he clearly knows which one of these lists is larger, using something like var z = first.Count >= second.Count ? first : second would eliminate several lines of code. — Thomas Lindvall, Mar 23 '15 at 14:24

score 1 · Answer 1 · edited May 23 '17 at 11:44

what your code is doing is merging two already sorted stacks. So it pretty much just traverses the stack and sees which value is smaller and then displays that one. Thus is you have two already sorted stacks it can merge them into one larger stack that is also already sorted.

By changing your code so the last item pushed into the first stack is 80 vs 7 it breaks this state and thus your logic is flawed. A different approach to solve this code might be to first merge the two stacks then pop them and sort them at that time. Here is a some code to sort a stack (dont click it if you want to try and figure it out yourself first)

You can also write some unit tests to confirm these scenarios are fixed as you modify your code.

Lastly if you compare your new sorting code to one of the examples maybe you can measure the difference in performance between the two like this example did

Sorting not working properly

1 Answers1