クイックソートの計数比較：間違った回答

Question

私はクイックソートで行われた比較回数を計算するコードを書いています。

アルゴリズムは、クイックソートが長さmの配列に対して実行されるたびに、比較回数をm-1だけ増加させます（ピボットはそれ自身以外のものと比較されるため）。

ピボットの選択は、常に配列の最初の要素です。

10000エントリの配列で使用しようとすると、間違った答えが出てきます。

正解はとします。データセットへ

リンクを以下に示す： https://drive.google.com/file/d/0B0D_kFnzj_RrYm9NT0lrM3JfN2c/view?usp=sharing

総比較をxに格納されています。

#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

この部分は間違っている：あなたは最後まで開始から行く必要はありません

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++; 
    } 
} 

。あなたはi> jまで開始する必要があります。興味深いの線があるがhttps://en.wikipedia.org/wiki/Quicksort

：

クイックソートがあるので、私はBを使用していないこのコードで

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; 
    } 
} 

は、リンクを参照してください"インプレース"アルゴリズムを使用しているため、結果を別の配列に保存する必要はありません