クイックソルトの実装でエラーが見つかりません

Question

このクイックソートアルゴリズムをいくつかの異なるピボット戦略で実装したいのですが、論理的なエラーがあります。私はそれを見つけるのを助けてくれますか？

#include <iostream.h> 
#include<stdlib.h> 
#include<stdio.h> 
#include<conio.h> 
int arr[100],i,pivot,left,right,sum=0,a,n=10; 

int partition(); 
void quickSort(int* ,int ,int); 



void main() 
{ 
    clrscr(); 
    int i,n=20; 
    for(i=0;i<=n;i++) 
    { 
     arr[i]=rand()%100; 
    } 

    for(i=0;i<=n;i++) 
    { 
     cout<<"\t"<<arr[i]; 
    } 

    quickSort(arr,n,i); 

    for(i=1;i<n;i++) 
    { 
     cout<<"\n"<<arr[i]; 
    } 

    getch(); 
} 

int partition() 
{ 
    // int i; 
    // int sum=0; 
    // int pivot; 
    // stable_sort(arr,arr+3); 
    for(i=0;i<5;i++) 
    { 
     cout<<"\nsorted k elements\t"<<arr[i]; 
     // sum=sum+arr[i]; 
    } 
    // cout<<sum; 
    //cout<<"median is "<<sum/3; 
    pivot=arr[(i)/2]; 
    cout<<"pivotis value at position "<<pivot ; 
    return pivot; 
} 

void quickSort(int arr[],int left,int right) 
{ 
     partition(); 
     right=n,left=0; 
     int i = right, j =left; 

     int tmp; 
     int p=pivot; 
     cout<<" m array of p"<<p; 
     while (i <= j) { 
     while (arr[i] < p) 
      i++; 
     while (arr[j] > p) 
      j--; 
     if (i <= j) { 
      tmp = arr[i]; 
      arr[i] = arr[j]; 
      arr[j] = tmp; 
      i++; 
      j--; 
     } 
    } 
    if (left < j) 
    { 
     quickSort(arr, left, j); 
    } 
    if (i < right) 
    { 
     quickSort(arr, i, right); 
    } 
} 

Answer 1

あなたのピボット値は、常に関係なく、一度にソートすることが起こるどの配列の一部、arr[2]あるarr[(i)/2]の値は、できなくなります。 leftとrightの値をpartitionに渡すので、現在の呼び出しで考慮する値はquickSortです。

はまた、あなたがquickSortに初期呼び出しに渡すleftとrightの値は、きっとあなたが意図したものではありませんこれは、それぞれ、20および21です。長さ100の配列があり、最初の21個の要素が初期化されているため、これらのパラメーターには0と21を渡すことをお勧めします。

しかし、あなたは異なるピボット戦略にクイックソートをテストしたい場合は、おそらく、最初にすべきことは、人は自分の教科書に示されたように、それは、典型的なピボット戦略最初の作業を取得することです。具体的にはのの実装から開始し、の場合はに変更してください。あなたは教科書やクラスノートで実用的な実装を見つけることができるはずです。

Answer 2

配列の値を比較する場所が見つかりませんでした。

私はあなたがこの場所を確認してくださいとします

if (i <= j) { 
     tmp = arr[i]; 
     arr[i] = arr[j]; 
     arr[j] = tmp; 
     i++; 
     j--; 
    } 

おそらくそれは次のようになります。

if (arr[i] < arr[j]) { 
     tmp = arr[i]; 
     arr[i] = arr[j]; 
     arr[j] = tmp; 
     i++; 
     j--; 
    }