c - Quicksort排序问题

Question

这可能不是进行快速排序的常规方法。我第一次尝试它。数字没有按应有的方式排序。我尝试对随机数字列表进行排序。但是我无法确定逻辑即使经过严格检查也会出错。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int n;
int *expivot;
int *arr;
void quicksort();
void display();
int check();

main()
{
    int i;
    printf("to continue press 'a' always\n");
    while(getch()=='a')
    {
        printf("Enter the length of list\n");
        scanf("%d",&n);
        time_t start,end;
        double t;
        start=clock();
        arr=(int *)calloc(n,sizeof(int));
        expivot=(int *)calloc(n,sizeof(int));
        srand(time(NULL));
        for(i=0;i<n;i++)
            arr[i]=rand()%RAND_MAX + 1;
        printf("\nelements inputted are:");
        display();
        quicksort();
        end=clock();
        t=(double)(end-start)/CLOCKS_PER_SEC;
        printf("\n\nelements sorted are:");
        display();
        printf("\ntime take is %.15lf",t);
        free(arr);
        free(expivot);
    }
}
void quicksort()
{
    int low,high,temp;
    int pivot=rand()%n;//generate random pivot
    int store=pivot;
    /*location of pivot might change due to swapping,so using store to store pivot      location so as to add this to expivot list after running quickort once*/
    int flag=1;
    if(expivot[pivot]==1)   // checks if it's an already used pivot
        flag=0;
    if(flag==1) //if the pivot is unused
    {
        low=pivot;
        high=pivot;
        while(low>0 && expivot[low]==0)
            low--;
        if(expivot[low]==1)//i
            low++;
        /*decrements low to a location where a value has been set permanently and then    increase by 1,if nothing is set then decrements low to zero*/
        /*increments high to a location where a value has been set permanently and then decrease by 1,if nothing is set then increments high to last index*/
        while(high<n-1 && expivot[high]==0)
            high++;
        if(expivot[high]==1)
            high--;
        while(low<high)
        {
            if(arr[low]>=arr[pivot] && arr[high]<=arr[pivot])//checks swap  possibilty
            {
                if(low==pivot)   //if pivot is to be swapped store new location of pivot
                    store=high;
                else if(high==pivot)
                    store=low;
                temp=arr[low];
                arr[low]=arr[high];
                arr[high]=temp;
                low++;
                high--;
            }
            else
            {
                if(arr[low]<arr[pivot])
                    low++;
                else if(arr[high]>arr[pivot])
                    high--;
            }
        }
        expivot[store]=1;
        /*final location of pivot,stores info that this location has a permanent value now
         and cannot be used as a pivot*/
    }
    if(check()==1)
        quicksort();
}


int check() //checks if there are any unused pivots
{
    int i;
    for(i=0;i<n;i++)
    {
        if(expivot[i]==0)
            return 1;
    }
    return 0;
}

void display()
{
    int i;
    for(i=0;i<n;i++)
        printf("%d ",arr[i]);
}

Answer 1

你的方法是:

1. 从整个数组中随机选择一个轴；
2. 从枢轴开始，向两个方向扩展一个范围，这个范围将被枢轴划分；
3. 所有数据透视表将缓存在另一个数组中(第 5 项)；
4. 上面第2项中提到的范围应该尽可能大，但是:1)不应超出整个数组的范围； 2) 不应包含另一个枢轴，如果包含，则停止并收缩一个单元；
5. 根据其展开的枢轴对范围进行分区，然后缓存该枢轴；
6. 如果数组中的所有单元都已被选为枢轴，则排序完成。如果没有，请一遍又一遍地重复上述操作。

你的代码存在三个问题:

1-“checd()”函数应该是:

int check() //checks if there are any unused pivots
{
    int flag = 0;
    int i;
    for(i=0;i<n;i++)
    {
        if(expivot[i]==0)
            flag = 1;
    }
    return flag;
}

你应该检查所有成员，看看他们是否ALL满足你的条件，但不是其中一个满足你的条件。

2- 在缩小范围的同时，确保枢轴在“高”和“低”之间(相等就好)。继续跟踪枢轴的索引和值。 while 循环应该是:

//"store" is not needed, change it to "pivot", even after this code block.
    while(low<high)
    {
        if(arr[low]>=arr[pivot] && arr[high]<=arr[pivot])//checks swap  possibilty
        {
            if(low==pivot)   //if pivot is to be swapped store new location of pivot
                pivot=high;
            else if(high==pivot)
                pivot=low;
            temp=arr[low];
            arr[low]=arr[high];
            arr[high]=temp;

            /////////////////////
            if (low < pivot)
                low++;
            if (high > pivot)
                high--;
            /////////////////////
        }
        else
        {
            if(arr[low]<arr[pivot])
                low++;
            else if(arr[high]>arr[pivot])
                high--;
        }
    }

3- 最后，从 calloc 或 malloc 获取内存后，检查它是否为 NULL。

================================== 另外，你应该确保数组中的所有单元都可以被选中，因为计算机中的随机数大多是伪随机数。因此，也许对于一定的长度，不能永远选择一个特定的单位。