1

だから私はクイックソートで遊んでいて、何か奇妙なことに気づきました。ソートする値が10を超えると、挿入ソートのようなものと比較して、ソートに非常に長い時間がかかります。10を超える値を並べ替えるように依頼するたびに、なぜこれほど遅いのか説明できますか？多分それはコードと関係があります。

編集。いくつか変更を加えましたが、スタックオーバーフローエラーが発生しました。

       public class quicksorttest{
   public static void main(String args[]){
      int array[] = new int[100];
      for(int a =0; a<array.length;a++){
         array[a] = (int)(Math.random()*100);
      }

      quickSort(array,0,array.length);
   }

   public static void quickSort(int array[],int p, int q){
    if(q-p <=1);//skip

    else{
        int x; int i,j,k;
        //let x = middle element in f[p..q-1]. 

        x= array[(p+q/2)];
        i=p;j=p;k=q;
        while(j!=k){
            if(array[j]==x)
                j=j+1;
            else if(array[j]<x){    //swap array[j] with array[i]
                int temp =array[j];
                array[j] = array[i]; array[i]=temp;
                j=j+1;i=i+1;

            }
            else{//array[j]>x
                //swap array[j[ with array[k-1]
                int temp = array[j]; 
                array[j] = array[k-1]; array[k-1]=temp;
                k=k-1;
            }
        }

        quickSort(array,p,i);
        quickSort(array,j,q);

    }
   }
}
4

1 に答える 1

0

私がアルゴリズム、特に再帰アルゴリズムにアプローチする方法は、次の大まかな計画に従うことです。

  • 空の配列から始める
  • 要素が 1 つの配列を試してください
  • 2 つの要素を持つ配列を試してください (これらの最初の 3 つは通常、再帰メソッドの最終状態であるため重要です)。
  • 3 つまたは 4 つの要素を持つ配列を試してみてください。ただし、結果を再現できるように、同じセットをしばらく試してみてください。ランダム セットでエラーが発生しても、次の実行で機能する場合、問題が修正されたのか、それとも試していたデータだったのかがわからない可能性があります。

上記の作業を繰り返し行って初めて、より大きなデータセットを試してから、最後にランダム化されたデータを試してください。

あなたの場合、小さな問題はほとんどありませんが、再帰的な問題では小さな問題が増える可能性があります! :-)

まず、上記の方法を試してください。それでも行き詰まる場合は、Bob Sedgewicks アルゴリズム サイトで、非常に優れたシンプルな実装を見つけることができます。

System.out.println ステートメントを追加する価値があります (小さなデータ セットの場合 - 大きなデータ セットの場合、これはあまり役に立ちません)。

于 2013-02-23T19:51:52.163 に答える