QuickSort Algorithm Anzahl der Vergleiche

Question

Ich habe eine Klasse bei Coursera genommen und wir hatten eine Zuweisung, die die Anzahl der Vergleiche zählen sollte, die QuickSort auf einem Array mit 10.000 Größen und Zahlen durchführt.

#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)); 

} 

Ich bekomme einen Segmentierungsfehler. Ich habe festgestellt, dass das Problem in zwei rekursiven Aufrufe von QuickSort liegt.

Ich habe keine Ahnung, wie Sie dieses Problem lösen, Ihre Hilfe würde sehr geschätzt werden Vielen Dank im Voraus.

Answer 1

Ich denke, der Code wie folgt sein sollte:

int QuickSort(...) { 
count++; 
if(r >l) 
... 

Partitionsfunktion:

for(j = l + 1; j <= r; j++) { 
    count++; 
    ... 

Hinweis: Zählung eine globale Variable auf 0 initialisiert wird;