算法2.8--快速排序的改进算法(QStackSort)

原书中给出的此算法的伪代码有误...faint,　以下代码可能有误，欢迎指正．

 

事情是这样的，比之于原来的快排，这个方法把递归改成了自己维护栈，而且是单侧进栈...

 

#include
#include
#include
#include

#define MAX_LENGTH 100
#define STACK_INCREASE 20

int curr;
int * list = NULL;
int * stack = NULL;
int * bottom = NULL;
int * top = NULL;
int stack_size = 0;

/*Show usage*/
void usage(char * prog)
{
        printf("%s Usage:\n", prog);
        printf("%s \n", prog);
}

/*Generate and initialize the list*/
int * generate_list(int count)
{

        int i;
        int * list;
        list = (int *)malloc(count*sizeof(int));
        if(list == NULL)
        {
                perror("malloc");
                return NULL;
        }

        /*Initialize the list with integers less than 100*/
        srandom((unsigned int)time(NULL));
        for (i  = 0; i < count ; i ++)
                list[i] = random()%100;

        return list;
}

/*Show the list*/
void show_list(int * list, int length)
{
        int i;
        for(i = 0; i < length; i ++)
                printf("%d      ", list[i]);

        printf("\n");
}

/*stack operations*/
int is_stack_empty()
{
        return bottom == top?1:0;
}

void show_stack()
{
        int *i;
        if(is_stack_empty())
        {
                printf("Stack is empty!\n");
                return ;
        }
        for(i = bottom; i < top; i ++)
                printf("%d ", *i);
        printf("\n");
}

void push_stack(int first, int last)
{
        int i = first-1;
        if(first > last)
                return;

        if(stack_size == 0)
        {
                stack = (int *)malloc(MAX_LENGTH * sizeof(int));
                top = stack;
                bottom = stack;
                stack_size = MAX_LENGTH;
        }
        else  if(stack_size - (top - bottom)/sizeof(int) <= 0) /*no space left in the stack*/
        {
                stack = (int *)realloc(stack, stack_size + STACK_INCREASE);
                stack_size += STACK_INCREASE;
        }
        while(i < last)
        {
                * top = list[i];
                top ++;
                i++;
        }
}

void pop_stack(int first, int last)
{
        int i = first -1;
        if(first > last)
                return ;

        while((i < last) && (top != bottom))
        {
                top--;
                i++;
        }
}

/*algorithm*/
int partition(int * list, int first, int last)
{
        int left = first -1;
        int right = last -1;
        int pivot = list[left];
        while(left < right)
        {
                while((right > left) && (list[right] >= pivot))
                        right --;
                if(left < right)
                {
                        list[left] = list[right];
                        left ++;
                }
                while((left < right) && (list[left] < pivot))
                        left ++;
                if(left < right)
                {
                        list[right] = list[left];
                        right --;
                }
        }
        list[left] = pivot;
        return (left + 1);
}

void qstack_sort(int * list, int length)
{
        int first = 1, last = length, i;
        push_stack(1, length);
        while(!is_stack_empty())
        {
                pop_stack(first, last);
                while(first < last)
                {
                        i = partition(list, first, last);
                        push_stack(i +1, last);
                        last = i-1;
                }
                first = i+1;
                last = length;
        }
        return;
}

int main(int argc, char * argv[])
{
        int length;
        struct timeval tpstart,tpend;
        float timeuse;

        /*Deal with the arguments*/
        if(argc != 2)
        {
                usage(argv[0]);
                exit(127);
        }

        length = atoi(argv[1]);
        if(!length || length > MAX_LENGTH)
        {
                usage(argv[0]);
                exit(129);
        }

        list = generate_list(length);
        if(list == NULL)
                exit(128);
        else
        {
                printf("Soruce list:\n");
                show_list(list, length);

                gettimeofday(&tpstart,NULL);
                qstack_sort(list, length);
                gettimeofday(&tpend,NULL);
                printf("Ordered list:\n");
                show_list(list, length);
                timeuse=1000000*(tpend.tv_sec-tpstart.tv_sec)+ tpend.tv_usec-tpstart.tv_usec;
                timeuse/=1000;
                printf("time used: %f msec\n", timeuse);
        }

        free(list);
        return 1;

}