1

私が見たYouTubeのアルゴリズムの視覚的なプレゼンテーションからクイックソートアルゴリズムを作成しましたが、再帰はまったく機能しません。:(これらの2行をコメントアウトすると、

quicksort(array,0,start-1);
quicksort(array,start+1,temp);

.. プログラムはクラッシュせず、出力は部分的に正しい 2,1,3,5,4 になります.. しかし、再帰に入るとクラッシュします。whileループ全体の後、開始は終了と同じになります..

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

void swap(int *a, int *b){

int temp = *a;
*a = *b;
*b = temp;
}

void quicksort(int *array, int start, int end){

int pivot = start;
int temp = end;     
while(start != end){

if(pivot==start){
    if(array[pivot] > array[end]){
    swap(&array[end],&array[pivot]);
    pivot = end;
    start++;
    }
    else
    end--;
}
else{
if(array[pivot] < array[start]){
    swap(&array[start],&array[pivot]);
    pivot = start;
    end--;
}  
else
start++;   

}               
}

quicksort(array,0,start-1);
quicksort(array,start+1,temp);
}




main(){

int x[5] = {3,1,5,2,4};
int i;
quicksort(x,0,4);
for(i=0;i<5;i++)
printf("%d ", x[i]);
getch();
}
4

3 に答える 3

2

欠けているのは、アルゴリズムをキャンセルするポイントです。quicksort関数の制御フローを確認すると、アプリケーションがこの関数を通過できるすべてのパスで関数が再度呼び出されることがわかります。いつ完了したかを確認するのは簡単です。パラメータとが等しい場合は、再度呼び出さずに関数を終了する必要があります。これでうまくいくはずです。quicksortstartend

于 2012-04-05T10:48:52.800 に答える
0

クラッシャーへ: あなたのコードには、再帰の終了条件がありません。これは、入力範囲が空であっても、再帰呼び出しを入力することを意味します (配列への負のインデックスを使用して、おそらくクラッシュを引き起こしています)。次のような条件を追加する必要があります

if(there's at most 1 element in the input range)
  return; // already sorted
于 2012-04-05T10:48:16.700 に答える