QuickSort 算法 比较次数 [英] QuickSort Algorithm Number of Comparisons

问题描述

我一直在 Coursera 上课，我们有一个作业是计算 QuickSort 对一个 10,000 大小的数组进行的比较次数.

I have been taking a class at Coursera and we had an assignment which was to count the number of comparisons QuickSort does on a 10,000 size array a numbers.

#include <stdio.h>
#define SIZE 10000

int ComparsionCount = 0;

void swap(int a[], int i, int j) {
        int temp = a[j];
        a[j] = a[i];
        a[i] = temp;
}
int partition(int a[], int l, int r){
        int p = a[l];
        int i = l + 1;
        int j;
        for (j = l + 1; j <= r; j++) {
            if (a[j] < p) {
                swap(a, j, i);
                i++;
            }
        }
        swap(a, l, i - 1);
        return (i - 1);
}
void add(int i) {
    ComparsionCount += i;
}

int QuickSort(int a[], int l, int r){
    int pivot;
    if (r > 1) {
        add(r - 1);
        pivot = partition(a, l, r);
        QuickSort(a, l, pivot - 1);
        QuickSort(a, pivot + 1, r);
    }
    return pivot;
}

int main() {
    FILE *fr;
    int arr[SIZE];
    int i = 0;
    int elapsed_seconds;
    char line[80];

    fr = fopen("QuickSort.txt", "r");
    while (fgets(line, 80, fr) != NULL)
    {
         /* get a line, up to 80 chars from fr.  done if NULL */
         sscanf (line, "%ld", &elapsed_seconds);
         /* convert the string to a int */
         arr[i] = atoi(line);
         i++;
    }
    fclose(fr);  /* close the file prior to exiting the routine */
    printf("%d\n",QuickSort(arr,0,SIZE-1));
}

我收到分段错误.我已经确定问题在于 QuickSort 的两次递归调用.

I am getting an segmentation error. I have identified that the problem lies in two recursive calls of QuickSort.

我不知道如何解决这个问题，非常感谢您的帮助提前致谢.

I have no idea of how to solve this problem,your help would be appreciated a lot Thanks in advance.

推荐答案

我觉得你应该在分区函数中添加这样的代码:

I think you should add the code in the partition function like this:

for (j = l + 1; j <= r; j++) {
    count++;
    if (a[j] < p) {
    ...
}

注意:count 是一个初始化为 0 的全局变量.

Note: count is a global variable initialized to 0.

这篇关于QuickSort 算法 比较次数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！