Zählen von Vergleichen in Quicksort: Falsche Antwort

Question

Ich habe Code geschrieben, um die Anzahl der in QuickSort durchgeführten Vergleiche zu berechnen.

Der Algorithmus erhöht die Anzahl der Vergleiche um m-1, wenn ein Quicksort auf einem Array der Länge m ausgeführt wird (Da Pivot mit allem außer sich selbst verglichen wird).

Die Wahl des Pivots ist immer das erste Element des Arrays.

Wenn ich versuche, es auf einem Array von 10000 Einträge zu verwenden, gibt es mir eine falsche Antwort.

Eine korrekte Antwort soll sein. https://drive.google.com/file/d/0B0D_kFnzj_RrYm9NT0lrM3JfN2c/view?usp=sharing

Die Gesamt Vergleiche in x gespeichert sind:

Der Link zu dem Datensatz ist unten angegeben.

#include<stdio.h> 
    long long x=0; 
    int size=10000; 
    int A[10000]; 
    int B[10000]; 

    void quicksort(int A[],int begin,int end) 
    { 
    if(begin<end){ 
    int i=begin; 
    int j=end; 
    int k; 
    int pivot=begin; 

    for(k=begin+1;k<=end;k++) 
    { 
    if(A[k]>A[pivot]) 
    { 
    x++; 
    B[j]=A[k]; 
    j--; 
    } 
    else 
    { 
    x++; 
    B[i]=A[k]; 
    i++; 
    } 
    } 

    B[i]=A[pivot]; 

    for(k=begin;k<=end;k++) 
    { 
    A[k]=B[k]; 
    } 

    quicksort(A,begin,i-1); 
    quicksort(A,i+1,end); 
    } 
    else 
    { 
    if((end-begin)==1) x++; 
    } 
    } 

    int main() 
    { 

    FILE *myFile; 
    myFile = fopen("QuickSort.txt", "r"); 


    int i; 
    for (i = 0; i < 10000; i++) 
    { 
    fscanf(myFile, "%d", &A[i]); 
    } 

    quicksort(A,0,size-1); 

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

    printf("%lld",x); 
    } 

Answer 1

dieser Teil ist falsch:

for(k=begin+1;k<=end;k++) 
{ 
    if(A[k]>A[pivot]) 
    { 
     x++; 
     B[j]=A[k]; 
     j--; 
    } 
    else 
    { 
     x++; 
     B[i]=A[k]; 
     i++; 
    } 
} 

Sie müssen von Beginn bis Ende nicht gehen. Du solltest nur von Anfang bis Anfang gehen.

siehe Link: https://en.wikipedia.org/wiki/Quicksort

dort die interessanten Linien sind:

do 
    i := i + 1 
while A[i] < pivot 
do 
    j := j – 1 
while A[j] > pivot 
if i >= j then 
    return j 
swap A[i] with A[j] 

c/C++

i = begin; 
j = end; 
while(true) 
{ 
    while(i< end && A[i] < A[pivot]) 
    { 
     i++; 
    } 
    while(j> begin && A[j] >= A[pivot]) 
    { 
     j--; 
    } 
    if(i<j) 
    { 
     int temp = A[i]; //std::swap(A[i],A[j]); 
     A[i] = A[j]; 
     A[j] = temp; 
    else 
    { 
     break; 
    } 
} 

In diesem Code verwende ich B nicht, weil quicksort eine ist "inplace" -Algorithmus und deswegen müssen wir das Ergebnis nicht in einem anderen Array speichern