C 地狱代码：快速排序程序运行无限循环：奇怪的情况

Question

我已经为 Quicksort 写了一个 C 代码，看起来完全没问题。但是代码不能完美地工作，并且在从数组中获取值时奇怪地进入无限循环或其他东西（我不知道），并且在那个获取值的循环之后什么都不做。

#include<stdio.h>
int flag=0;
int partition(int *,int,int);
void quicksort(int *A,int low, int high)          //Code for quicksort function
{
    int pivot;
    printf("%d",flag);
    flag++;
    if(low<high)
    {
     pivot =partition(A,low,high);        //calls partition function
     quicksort(A,low,pivot);
     quicksort(A,pivot,high);
    }
}
//code for partition function
int partition(int *A,int low,int high)
{
    int pivot,left,right,temp;
    pivot=A[low];
    left=low;
    right=high;
    printf("%d",flag);
    flag++;
    while(left<right)
        {
         while(A[left]<pivot)
            left++;
         while(A[right]>pivot)
            right++;
         if(left<right)
            {
             temp=A[left];
             A[left]=A[right];
             A[right]=temp;
            }
        }
    temp=A[right];
    A[right]=A[left];
    A[left]=temp;
    return right;
}

int main()
    {
        int a[10],i,n;
        printf("\n***QUICK SORT***");
        printf("\nENTER THE NUMBERS OF ENTRIES:");
        scanf("%d",&n);

        printf("\nENTER THE ENTRTIES IN ARRAY:");
        //PROBLEM IS IN THIS LOOP OR ELSE (I DONT KNOW WHAT EXACTLY WHAT THE PROBLEM IS)

        for(i=0;i<n;i++)
        {
            printf("i=%d\n",i);
            scanf("%d",&a[i]);     
        }
        //IF WE COMMENT THIS BELOW LINE OF FUNCTION CALL THEN LOOP WORKS FINE
        quicksort(a,0,n-1);    //passes the array and first and last element

        printf("\nTHE SORTED ARRAY IS:\n");
        for(i=0;i<n;i++)
            printf(" %d \n ",a[i]);
        return 0;
    }

Answer 1

正如许多人在您对代码的评论中所指出的那样。您需要重新考虑快速排序算法的分区步骤 - 您遇到无限循环的原因是在交换之后，left 和 right 永远不会更新导致无限循环。

这不是我自己的，但在我学习复杂的排序算法时对我有帮助：

void quickSort(int arr[], int left, int right) {
  int i = left, j = right;
  int tmp;
  int pivot = arr[(left + right) / 2];
  /* partition */
  while (i <= j) {
        while (arr[i] < pivot)
              i++;
        while (arr[j] > pivot)
              j--;
        if (i <= j) {
              tmp = arr[i];
              arr[i] = arr[j];
              arr[j] = tmp;
              i++;
              j--;
        }
  };

您可能会发现这很有帮助，而且正如许多人所说，您可能需要清理代码以帮助进行调试。

Answer 2

似乎 right++; 应该是 right--; 或者两边都增加。

Answer 3

在你的函数中 quicksort()

quicksort(A,low,pivot);
quicksort(A,pivot,high);

这些参数应该是这样的-

quicksort(A,low,pivot-1);  
quicksort(A,pivot+1,high);

函数中partition()

     while(A[right]>pivot)
        right++;

在此循环中 right 应递减

    while(A[right]>pivot)
        right--;

最后这个函数中的交换

 temp=A[right];
 A[right]=A[left];
 A[left]=temp;

但实际上right应该是pivot

的最后一个位置

 A[left]=A[right]
 A[right]=pivot

只是一个建议，请在 main 函数中增加数组的大小 a[]。

Answer 4

正如许多评论者已经指出的那样，这段代码中有很多问题，我只是想向您展示一个实际有效的实现，包括（希望）对所做的事情有帮助的评论：

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

#define CHUNK_SIZE 16

static void quicksort_rec(int *l, int *r)
{
    int *p, *ll, *rr, t;

    if (r-l < 1) return; /* only one element left -> nothing to sort */

    p = r;      /* use last element for pivot (any element would do) */
    rr = r-1;   /* pointer to last element to compare with pivot */
    ll = l;     /* pointer to first element to compare with pivot */

    while (1)
    {
        /* move ll until we find something greater than pivot on the left */
        while (ll <= rr && *ll <= *p) ++ll;

        /* move rr until we find something smaller than pivot on the right */
        while (ll <= rr && *rr >= *p) --rr;

        /* ll and rr met? then we're done with this step */
        if (rr <= ll)
        {
            /* swap pivot to the "meeting position" */
            t = *p;
            *p = *ll;
            *ll = t;

            /* sort partitions recursively */
            quicksort_rec(l, ll-1);
            quicksort_rec(ll+1, r);

            /* done */
            return;
        }

        /* swap greater element on the left with smaller element on the right */
        t = *rr;
        *rr = *ll;
        *ll = t;
    }
}

static void quicksort(int *v, int num)
{
    quicksort_rec(v, v+num-1);
}


int main()
{
    char buf[64];       /* buffer for user input */
    int *values;        /* pointer to dynamically allocated array */
    int avail;          /* number of currently free slots in the array */
    int entries = 0;    /* number of total entries in the array */
    int i;              /* iterating variable */

    puts("Quicksort Example\n"
         "=================\n"
         "\n"
         "Enter whole numbers to sort, just hitting enter starts sorting.\n");

    /* allocate first chunk of memory */
    values = malloc(CHUNK_SIZE * sizeof(int));

    if (!values)
    {
        perror("malloc");
        exit(1);
    }
    avail = CHUNK_SIZE;

    while (1)
    {
        fputs("Please enter next number: ", stdout);

        /* try reading user input, if impossible, break */
        if (!fgets(buf, 64, stdin)) break;

        /* if input is empty, break */
        if (buf[0] == '[=10=]' || buf[0] == '\r' || buf[0] == '\n') break;

        /* convert input to integer as next value for array */
        values[entries] = atoi(buf);
        printf("Added `%d' to sort list\n", values[entries]);
        ++entries;

        /* check whether there is space left in the array */
        if (!--avail)
        {
            /* if not, increase array size by the next chunk */
            values = realloc(values, (entries + CHUNK_SIZE) * sizeof(int));
            if (!values)
            {
                perror("realloc");
                exit(1);
            }

            /* reset available slots to size of chunk */
            avail = CHUNK_SIZE;
        }
    }

    printf("Now sorting %d elements with quicksort.\n", entries);

    /* sort the array */
    quicksort(values, entries);

    puts("Result:");

    for (i = 0; i < entries; ++i)
    {
        printf("%d\n", values[i]);
    }

    free(values);
    return 0;
}

C 地狱代码：快速排序程序 运行 无限循环：奇怪的情况

C Code of hell : quick sort program running to infinite loop : weird situation

c

quicksort

C 地狱代码：快速排序程序运行无限循环：奇怪的情况