c - 尝试使用随机编号时 QuickSort.C 段错误。发电机

Question

这是一个用 C 编写的快速排序程序，该程序编译没有任何错误。但是当运行并选择随机数进行排序时。我得到的输出如下，

sam@TechTosh ~ $ gcc quick.c
sam@TechTosh ~ $ ./a.out

1> Read from file
2> Random no. Generator


Enter the Choice
2
Starting 10
Segmentation fault

这是程序，我已经从这个程序中调试了很多错误，最后它运行了，但无法排序，也没有从从文件读取或随机数生成这两种类型的输入中获取输入。

#include<stdio.h>
#include<time.h>
#include<values.h>
#include<malloc.h>
#include<stdlib.h>
#include<unistd.h>
int *a;
void swap(int i,int j)
{
    int temp;
    temp=a[i];
    a[i]=a[j];
    a[j]=temp;
}
int partition(int l,int r)
{
    int p,i,j;
    p=a[l];
    i=l;
    j=r+1;
    while(i<j)
    {   
        for(i=i+1;i<r&&a[i]<p;i++)
            for(j=j-1;j>l&&a[i]>p;j++)
                swap(i,j);
    }
    swap(i,j);
    swap(l,j);
    return j;
}
void quick(int l,int r)
{
    int s,i;
    if(l<r)
    {
        s=partition(l,r);
        //delay(1);
        quick(l,s-1);
        quick(s+1,r);
    }
}
void main()
{
    FILE *fp,*fp1;
    clock_t c1,c2;
    int n,i,j,l,r,datasize=1,ch,x,c;
    long int m;
    char file[10];
    do
    {
        printf("\n1> Read from file\n2> Random no. Generator\n\n");
        printf("\nEnter the Choice\n");
        scanf("%d",&ch);
        switch(ch)
        {
            case 1: printf("\nEnter n value\n");
                scanf("%d",&n);
                a=(int*)calloc(n,sizeof(int));
                printf("Enter the filename\n");
                scanf("%s",file);
                fp1=fopen(file,"r");
                i=0;
                while(!feof(fp1))
                {
                    fscanf(fp1,"%d",&a[i]);
                    i++;
                }
                fclose(fp1);
                for(i=0;i<n;i++)
                    printf("%d\t",a[i]);
                quick(0,n-1);
                printf("\nSorted Elements are\n");
                for(i=0;i<n;i++)
                    printf("%d\t",a[i]);
                free(a);
                break;
            case 2: m=100;
                fp=fopen("new.dat","w");
                while(datasize<=10)
                {
                    printf("Starting %ld\n",m);
                    a=(int*)calloc(m,sizeof(int));
                    for(i=0;i<=m-1;i++)
                    {
                        a[i]=rand()%MAXINT;
                        printf("%d",a[i]);
                    }
                    c1=clock();
                    quick(0,m-1);
                    c2=clock();
                    free(a);
                    fprintf(fp,"%ld\t %ld\n",m,(c2-c1)/CLOCKS_PER_SEC);
                    datasize++;
                    m=m+100;
                }
                fclose(fp);
                break;
            default: break;
        }
        printf("To continue, Press 1 else other for Exit!");
        scanf("%d",&c);
    }
    while(c==1);
}

Answer 1

您的递归不会结束，因为您的分区代码无法正常工作。这是代码的经过检测和稍微清理的版本(仍然有许多问题需要修复):

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

#define MAXINT INT_MAX

static int *a;

static void swap(int i, int j)
{
    int temp;
    temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

static int partition(int l, int r)
{
    printf("-->> %s: (%d, %d)\n", __func__, l, r);
    int p, i, j;
    p = a[l];
    i = l;
    j = r + 1;
    while (i < j)
    {
        for (i = i + 1; i < r && a[i] < p; i++)
            for (j = j - 1; j > l && a[i] > p; j++)
                swap(i, j);
    }
    swap(i, j);
    swap(l, j);
    printf("<<-- %s: (%d, %d) => %d\n", __func__, l, r, j);
    return j;
}

static void quick(int l, int r)
{
    int s;
    printf("-->> %s: (%d, %d)\n", __func__, l, r);
    if (l < r)
    {
        s = partition(l, r);
        // delay(1);
        quick(l, s - 1);
        quick(s + 1, r);
    }
    printf("<<-- %s: (%d, %d)\n", __func__, l, r);
}

int main(void)
{
    FILE *fp, *fp1;
    clock_t c1, c2;
    int n, i, datasize = 1, ch, c;
    long int m;
    char file[10];
    do
    {
        printf("\n1> Read from file\n2> Random no. Generator\n\n");
        printf("\nEnter the Choice\n");
        scanf("%d", &ch);
        switch (ch)
        {
        case 1:
            printf("\nEnter n value\n");
            scanf("%d", &n);
            a = (int *)calloc(n, sizeof(int));
            printf("Enter the filename\n");
            scanf("%s", file);
            fp1 = fopen(file, "r");
            i = 0;
            while (!feof(fp1))
            {
                fscanf(fp1, "%d", &a[i]);
                i++;
            }
            fclose(fp1);
            for (i = 0; i < n; i++)
                printf("%d\t", a[i]);
            quick(0, n - 1);
            printf("\nSorted Elements are\n");
            for (i = 0; i < n; i++)
                printf("%d\t", a[i]);
            free(a);
            break;
        case 2:
            m = 10;
            fp = fopen("new.dat", "w");
            while (datasize <= 10)
            {
                enum { PER_LINE = 7 };
                printf("Starting %ld\n", m);
                a = (int *)calloc(m, sizeof(int));
                for (i = 0; i <= m - 1; i++)
                {
                    a[i] = rand() % MAXINT;
                    printf("%11d", a[i]);
                    if (i % PER_LINE == PER_LINE - 1)
                        putchar('\n');
                }
                if (i % PER_LINE != 0)
                    putchar('\n');
                printf("Sorting\n");
                c1 = clock();
                quick(0, m - 1);
                c2 = clock();
                printf("Sorted\n");
                free(a);
                fprintf(fp, "%ld\t %ld\n", m, (c2 - c1) / CLOCKS_PER_SEC);
                datasize++;
                m = m + 10;
            }
            fclose(fp);
            break;
        default:
            break;
        }
        printf("To continue, Press 1 else other for Exit!");
        scanf("%d", &c);
    } while (c == 1);
    return 0;
}

输出开始于:

1> Read from file
2> Random no. Generator

Enter the Choice
Starting 10
      16807  282475249 1622650073  984943658 1144108930  470211272  101027544
 1457850878 1458777923 2007237709
Sorting
-->> quick: (0, 9)
-->> partition: (0, 9)
<<-- partition: (0, 9) => 10
-->> quick: (0, 9)
-->> partition: (0, 9)
<<-- partition: (0, 9) => 10
-->> quick: (0, 9)
-->> partition: (0, 9)
<<-- partition: (0, 9) => 10
-->> quick: (0, 9)
-->> partition: (0, 9)
<<-- partition: (0, 9) => 10
-->> quick: (0, 9)
-->> partition: (0, 9)
<<-- partition: (0, 9) => 10

…lots more of this…    

-->> quick: (0, 9)
-->> partition: (0, 9)
<<-- partition: (0, 9) => 10
-->> quick: (0, 9)
-->> partition: (0, 9)
<<-- partition: (0, 9) => 10
-->> quick: (0, 9)
-->> partition: (0, 9)
<<-- partition: (0, 9) => 10
-->> quick: (0, 9)
-->> partition: (0, 9)
<<-- partition: (0, 9) => 10
-->> quick: (0, 9)
Segmentation fault: 11

注意我是如何进行调试的——在关键位置添加适当的打印语句。从来没有一行以 <<-- quick: 开头，因此快速排序算法永远不会返回。