0

私は初心者の C プログラマーで、長い間このアルゴリズムに取り組んできました。正しい非減少ソートシーケンスを取得できなかったため、非常にイライラしています。

すべてのヘルプは大歓迎です。前もって感謝します。

これが私のコードです：

#include <stdio.h>
#include <conio.h>

int swap(short* a, short fst , short scnd){
    short temp  = a[fst] ;
    a[fst]          = a[scnd] ;
    a[scnd]         = temp ;

    return 0 ;
}

int div(short* a ,short p,short middle ,short r){
    while( p < r ){
        if( p < middle ){       
            if( a[p]      > a[middle] ){
                swap(a ,p ,middle) ; 
            }
            p++ ; 
        }
        if( middle < r ){
            if( a[middle] > a[r] ){
                swap(a ,middle , r) ;      
            }         
            r-- ;
        }
    }

    return 0 ;
}

int fast(short* a , short p , short r){
    if( p < r){
        int middle = (p+r)/2 ;
        div(a, p, middle ,r ) ;
        fast(a, p ,middle-1 ) ;
        fast(a ,middle+1 ,r);
    }
}

int main(){
    short n ,i ;
    scanf("%hd",&n);
    short a[n+1] ;
    for(i=1 ; i<=n ; i++ ){
        scanf("%hd",&a[i]);
    }

    fast(a ,1 ,n ) ;
    i=1;
    while(i<=n){
        printf("%hd " , a[i]);
        i++ ;
    }
    getch() ;
    return 0 ;
}
4

3 に答える 3

1

The bug is in the div function itself, that didn't follow the QuickSort logic. You could fin working code here Quicksort algorithm

I would recommend to copy-paste the code and get inspired by it's coding-standard too, including comments :)

于 2012-08-29T18:32:50.930 に答える
0

div 関数を変更して、パーティションの結果のインデックスを返すようにします。そうすれば、 fast() 関数で、分割点の両側で再帰できます。これにより、ロジックがクリーンアップされ、div 関数を分離してテストし、ロジックの弱点を簡単に見つけることができるようになります (間違いなく div() 関数にあります)。

現在、あなたのコードは分割が常に真ん中で起こると想定しているように見えますが、これはクイックソートの場合は必ずしもそうではありません (実際、これはクイックソートの微妙なポイントの 1 つです)。

パーティション関数の例を次に示します。

// please forgive any C-syntax errors not my best language
// low and high indicate a segment of the array to partition
// returns the index between low and high which serves as
// the partition point
int partition(short a[], int low, int high){
  int partition = low;
  int pivot = high;  // sub-optimal when a is already sorted
  for(int i=low; i<high; i++){
    if(a[i] < a[pivot]){
      swap(&a[i], &a[partition]);
      partition++;
    }
  }
  // places the pivot into its final sorted position at partition
  swap(&a[partition], &a[pivot]);
  return partition;
}

これは次のように再帰的に使用できます

sort(short a[], int low, high){
  if(high-low > 0){
    int partition = partition(a, low, high);
    // recurse to left and right of partition
    sort(a, low, partition-1);
    sort(a, partition+1, high);
  }
}
于 2012-08-29T20:51:43.220 に答える
0

1 つのデータ seq:
index:1 2 3 4 5 6 7
data: 1 2 0 10 8 4 5
middle: (1 + 7) / 2 = 4
a[middle]=10
関数 div は何を望んでいますか?

于 2012-08-29T22:42:50.190 に答える