title: quick sort using stack in c
body: <p>In a C assignment, I need to implement quick sort using a stack and without recursion.</p>
  
  <p>This is the function header (arr is the array to be sorted, size is its size):</p>
  
  <p><code>void StackBasedQuickSort(int* arr, int size)</code></p>
  
  <p>Assume a working Stack struct, and the following working functions (which were given to us as part of the asignment and cannot be changed):</p>
  
  <ol>
  <li><p><code>CreateStack(int size)</code> - creates a stack of given size.</p></li>
  <li><p><code>QuicksortDataStructureLimit(int size)</code> - returns the stack's desired size, calculated by 2*ceil(log(size)).</p></li>
  <li><p><code>IsStackEmpty(Stack* stack)</code> - return TRUE if stack is empty, false otherwise.</p></li>
  <li><p><code>IsStackFull(Stack* stack)</code> - return TRUE if stack is full, false otherwise.</p></li>
  <li><p><code>IsValidSubArray(int p, int r, int size)</code> - return TRUE if (0 &lt;= p &lt; r &lt; size), false otherwise</p></li>
  <li><p><code>MaybePushIndices(Stack* stack, int p, int r, int size)</code> - If a valid sub-array (see 5), pushes p and then r to the stack. Otherwise, does nothing.</p></li>
  <li><p><code>Pop(Stack* stack)</code> - pops an integer from the stack.</p></li>
  <li><p><code>SwapIndices(int* arr, int p, int q)</code> - Swaps 2 elements in an array.</p></li>
  </ol>
  
  <p>I've also implemented a Partition function, which I'm pretty sure works:</p>
  
  <pre><code>int Partition(int* arr, int p, int r) {
      int pivot = arr[r];
      int q = p;
      int j;
  
      for (j = p; j &lt; r; j++) {
          if (arr[j] &lt; pivot) {
              SwapIndices(arr, q, j);
              q++;
          }
      }
      SwapIndices(arr, q, r);
  
      return q;
  }
  </code></pre>
  
  <p>I've managed to implement the quick sort well using 2 different ways:</p>
  
  <p>First way:</p>
  
  <pre><code>void StackBasedQuickSort(int* arr, int size) {
  
      Stack* stack = CreateStack(QuicksortDataStructureLimit(size));
  
      MaybePushIndices(stack, 0, size - 1, size);
      while (!IsStackEmpty(stack)) {
          q = Pop(stack);
          p = Pop(stack);
          r = Partition(arr, p, q);
          if (IsStackFull(stack)) // for debugging
              printf("Stack is full(1st attempt)\n");
          MaybePushIndices(stack, p, r - 1, size);
          if (IsStackFull(stack)) // for debugging
              printf("Stack is full(2nd attempt)\n");
          MaybePushIndices(stack, r + 1, q, size);
      }
  
      FreeStack(stack);
  
  }
  </code></pre>
  
  <p>And the second way:</p>
  
  <pre><code>void StackBasedQuickSort(int* arr, int size) {
  
      Stack* stack = CreateStack(QuicksortDataStructureLimit(size));
  
      p = 0;
      r = size - 1;
      if (!(IsValidSubArray(p, r, size))) return;
      do{
          while (IsValidSubArray(p, r, size)) {
              q = Partition(arr, p, r);
              PrintStackQuickSortState(stack, arr, p, q, r, size);
              if (IsStackFull(stack) &amp;&amp; IsValidSubArray(q + 1, r, size))  // for debugging
                  printf("STACK FULL!\n");
              MaybePushIndices(stack, q + 1, r, size);
              r = q - 1;
          }
          if (!(IsStackEmpty(stack))) {
              r = Pop(stack);
              p = Pop(stack);
          }
          else
              break;
      } while (IsValidSubArray(p, r, size));
  
      FreeStack(stack);
  
  }
  </code></pre>
  
  <p>Now, here's my problem:
  Both ways work with a bigger stack, but both ways don't work with the given stack size, which is part of the assignment and cannot be changed (i.e. the first way gives "Stack is full(2nd attempt)" warnings, and the second way gives "STACK FULL!" warnings, with the sort not working when warnings are given but working when warnings are not given).</p>
  
  <p>Also, please take into account that I can only change the implementation of the Partition and StackBasedQuickSort functions. </p>
  
  <p>Is there a way to implement this stack-based quick sort in a way that doesn't need more than a 2*ceil(log(size)) -sized stack?</p>
  
  <p>Thanks!</p>
  
  <p>EDIT:
  In order to save more space on the stack, I've implemented an algorithm that pushes the indices of the smaller section to the stack and iteratively runs on the bigger part, but I am still using too much space on the stack (i.e. I get a "STACK FULL!" output, but the algorithm works well when I don't).</p>
  
  <p>New code:</p>
  
  <pre><code>Stack* stack = CreateStack(QuicksortDataStructureLimit(size));
  int p = -1, q = -1, r = -1;
  
  p = 0;
  r = size - 1;
  if (!(IsValidSubArray(p, r, size))) 
      return;
  else 
      q = Partition(arr, p, r);
  while (1){ // will break when stack is empty
      while (IsValidSubArray(p, q - 1, size) || IsValidSubArray(q + 1, r, size)){
          if (q - 1 - p &gt; r - q - 1){ // left &gt; right (push right, iterate left)
              if (IsValidSubArray(q + 1, r, size) &amp;&amp; IsStackFull(stack))
                  printf("STACK FULL!\n");
              MaybePushIndices(stack, q + 1, r, size);
              r = q - 1;
              q = Partition(arr, p, r);
          }
          else{ // right &gt;= left (push left, iterate right)
              if (IsValidSubArray(p, q - 1, size) &amp;&amp; IsStackFull(stack))
                  printf("STACK FULL!\n");
              MaybePushIndices(stack, p, q - 1, size);
              p = q + 1;
              q = Partition(arr, p, r);
          }
      }
      if (!(IsStackEmpty(stack))){
          r = Pop(stack);
          p = Pop(stack);
          if (IsValidSubArray(p, r, size))
              q = Partition(arr, p, r);
          PrintStackQuickSortState(stack, arr, p, q, r, size);
      }
      else
          break;
  }
  
  FreeStack(stack);`
  </code></pre>
  
  <p>Can anyone advice on making this work?</p>