C: QuickSort following the book "Schaum's Outlines"

Question

Please make some comment about this code of QuickSort.

My code is based on the example shown in this book.

#include <stdio.h>
#include <conio.h>
#include <math.h>

#define SIZE 12

struct StackItem
{
    int StartIndex;
    int EndIndex;
};
struct StackItem myStack[SIZE * SIZE];
int stackPointer = 0;

int myArray[SIZE] = {11,44,33,55,77,90,40,60,99,22,88,66};

void Push(struct StackItem item)
{
    myStack[stackPointer] = item;
    stackPointer++;
}

struct StackItem Pop()
{
    stackPointer--;
    return myStack[stackPointer];
}

int StackHasItem()
{
    if(stackPointer>0)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

void ShowStack()
{
    int i =0;

    printf("\n");

    for(i=0; i<stackPointer ; i++)
    {
        printf("(%d, %d), ", myStack[i].StartIndex, myStack[i].EndIndex);
    }

    printf("\n");
}

void ShowArray()
{
    int i=0;

    printf("\n");

    for(i=0 ; i<SIZE ; i++)
    {
        printf("%d, ", myArray[i]);
    }

    printf("\n");
}

void Swap(int * a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

int Scan(int *startIndex, int *endIndex)
{
    int partition = 0;
    int i = 0;

    if(*startIndex > *endIndex)
    {
        for(i=*startIndex ; i>=*endIndex ; i--)
        {
            if(myArray[i]<myArray[*endIndex])
            {
                Swap(&myArray[i], &myArray[*endIndex]);
                *startIndex = *endIndex;
                *endIndex = i;
                partition = i;
                break;
            }
            if(i==*endIndex)
            {
                *startIndex = *endIndex;
                *endIndex = i;
                partition = i;
            }
        }
    }
    else if(*startIndex < *endIndex)
    {
        for(i=*startIndex ; i<=*endIndex ; i++)
        {
            if(myArray[i]>myArray[*endIndex])
            {
                Swap(&myArray[i], &myArray[*endIndex]);
                *startIndex = *endIndex;
                *endIndex = i;
                partition = i;
                break;
            }
            if(i==*endIndex)
            {
                *startIndex = *endIndex;
                *endIndex = i;
                partition = i;
            }
        }
    }

    return partition;
}

int GetFinalPosition(struct StackItem item1)
{
    struct StackItem item = {0};
    int StartIndex = item1.StartIndex ;
    int EndIndex = item1.EndIndex;
    int PivotIndex = -99;

    while(StartIndex != EndIndex)
    {
        PivotIndex = Scan(&EndIndex, &StartIndex);

        printf("\n");
    }

    return PivotIndex;
}

void QuickSort()
{
    int splitPoint = 0; 
    struct StackItem item;  
    struct StackItem item1={0};
    struct StackItem item2={0};

    item.StartIndex = 0;
    item.EndIndex = SIZE-1;

    Push(item);

    while(StackHasItem())
    {
        item = Pop();

        splitPoint = GetFinalPosition(item);

        if(splitPoint>=0 && splitPoint<=(SIZE-1))
        {
            if(item.StartIndex <= (splitPoint-1))
            {
                item1.StartIndex = item.StartIndex;
                item1.EndIndex = splitPoint-1;
                Push(item1);
            }       
            if((splitPoint+1) <= item.EndIndex)
            {
                item2.StartIndex = splitPoint+1;
                item2.EndIndex = item.EndIndex;
                Push(item2);
            }
        }
    }
}

main()
{
    ShowArray();
    QuickSort();
    ShowArray();
}

Answer 1

You've implemented your own stack. C has a perfectly good stack, so don't make your own. Use recursive functions.

"Scan" means to look for something, but you modify the list while scanning. Its not a good name for the function

"GetFinalPosition" begins with Get which usually indicates the the function doesn't modify anything.

Answer 2

This doesn't look like any quicksort I'd know -- the logic's so convoluted I'm surprised it works at all. I would recommend taking a look at this question since it covers the same topic as yours.

I would suggest implementing this exercise in a recursive fashion first since it's typically easier than its iterative counterpart.

As Winston already mentioned, the function names you chose does not correctly reflect what that function is really doing. Go through each of your functions and try to come up with a description that accurately describes what it is trying to do. If you have to use the conjuction 'and' in that description then that function probably has too many responsibilities.

Here are some guiding questions to help you critique your own code:

• Are there any duplicate code present? This includes copy-and-pasted code with special tweaks to get the desired behavior.
• What are the preconditions, postconditions and invariants assumed for each of your functions above?
• How many things are each of your functions doing? List and enumerate them.
• Are those things related or unrelated to each other?
• Does the function name reflect that?
• Your push() and pop() manipulates the number of elements on the statically allocated stack. What happens if you push and pop beyond the minimum/maximum range permissible?(This is related to point #2)

Lastly, the book that you linked is quite old if the reviews are any indication(published in 1986). TCPL is the usual recommended source for learning C programming.

Answer 3

In addition to what the others said: I'd dump the #include <conio.h> as it is not platform independent and not needed either (like math.h).

Answer 4

You want us to make comments about your code, but I think what your code needs are comments.

/* comment */

Answer 5

Your test harness (main(), ShowArray(), etc) should be in its own module.

The QuickSort() function implementation should be in a separate .c file with the interface defined in a corresponding .h file.