Quick sort using a stack in c

Question

Quick sort using a stack in c

In assignment C, I need to do a quicksort using the stack and no recursion.

This is the function header (arr is a sorted array, size is its size):

void StackBasedQuickSort(int* arr, int size)

Let's assume a Stack working structure and the following working functions (which were provided to us as part of the assignment and cannot be changed):

CreateStack(int size)

- creates a stack of the specified size.
QuicksortDataStructureLimit(int size)

- returns the desired stack size calculated by 2 * ceil (log (size)).
IsStackEmpty(Stack* stack)

- return TRUE if the stack is empty, otherwise - false.
IsStackFull(Stack* stack)

- return TRUE if the stack is full, false otherwise.
IsValidSubArray(int p, int r, int size)

- return TRUE if (0 <= p <r <size), false otherwise
MaybePushIndices(Stack* stack, int p, int r, int size)

- If a valid subarray (see 5), then p and then r on the stack. Otherwise it does nothing.
Pop(Stack* stack)

- pops an integer from the stack.
SwapIndices(int* arr, int p, int q)

- swap 2 elements in an array.

I also implemented the Partition feature, which I'm sure works:

int Partition(int* arr, int p, int r) {
    int pivot = arr[r];
    int q = p;
    int j;

    for (j = p; j < r; j++) {
        if (arr[j] < pivot) {
            SwapIndices(arr, q, j);
            q++;
        }
    }
    SwapIndices(arr, q, r);

    return q;
}

I was able to quickly implement sorting using two different ways:

First way:

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);

}

And the second way:

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) && 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);

}

Now here is my problem: Both methods work with a large stack, but both methods do not work with a given stack size, which is part of the job and cannot be changed (ie the first method gives "Warnings full (second try)", and the second it gives "STACK FULL!" warnings when sorting doesn't work, when warnings are given, but works when no warnings are given).

Also note that I can only change the implementation of the Partition and StackBasedQuickSort functions.

Is there a way to implement this stack-based sort in such a way that it doesn't need a stack of 2 * ceil (log (size))?

Thank!

EDIT: To save more stack space, I've implemented an algorithm that pushes the indices of the smaller partition towards the stack and works iteratively for the most part, but I'm still using too much stack space (i.e. I get the output "STACK FULL!" but the algorithm works well when I don't).

New 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 > r - q - 1){ // left > right (push right, iterate left)
            if (IsValidSubArray(q + 1, r, size) && IsStackFull(stack))
                printf("STACK FULL!\n");
            MaybePushIndices(stack, q + 1, r, size);
            r = q - 1;
            q = Partition(arr, p, r);
        }
        else{ // right >= left (push left, iterate right)
            if (IsValidSubArray(p, q - 1, size) && 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);`