0

ソートアルゴリズムについてできる限りのことを学ぼうとしています。今日の議題はクイックソートです。これが私が得たものです。

クイックソート クラス:

import java.util.*;

  public class QuickSort{
    public static void swap(int A[], int x ,int y){
      int temp = A[x];
      A[x] = A[y];
      A[y] = temp;
    }

     public static int[] QSort(int A[], int L, int U){
       Random randomGenerator = new Random();

       if (L >= U){
         System.out.printf("The value of L: %d, U: %d\n",L,U);
         return A; // Sorted.

       }

       if (L < U ){
         int randomInt = randomGenerator.nextInt(U);
         swap( A, L, randomInt);
         int T = A[L];
         int M = L;

       for (int i = L+1;i < U; i++){
         if ( A[i] < T){
           M = M+1;
           swap(A, M, i);
         }
       }
       swap(A, L, M);
       QSort(A, L, M-1 );
       QSort(A, M+1, U );
    }

     //System.out.println(Arrays.toString(A));
     return A;
   }

 }

メイン:

 import java.util.*;

 public class Main{
   public static void main(String [] args){

     int[] intArray =  {1,3,2,4,56,0,4,2,4,7,80,120,99,9,10,67};

     System.out.printf("Original Array was: %s\n\n",Arrays.toString(intArray));

     System.out.printf("Size of Array is: %d\n",intArray.length);
     QuickSort qs = new QuickSort();
     int[] A = qs.QSort(intArray, 5, intArray.length);
     System.out.println(Arrays.toString(intArray));
 }

}

さて、それは今まで持っているすべてです。コードがコンパイルされ、並べ替えアルゴリズム以外のすべてが間違っています。私は QuickSort アルゴリズムで何が起こっているのかを論理的に理解しようとしており、プログラミング Perls という本を使用して理解を助けました。

ここに私が持っている質問のリストがあります:

  1. 本によると、forループのQuickSortクラスでは、「i's」条件節は「i <= U」である必要がありますが、そうすると、コードで「配列インデックスが範囲外です」というエラーが表示されます。なぜそれが起こっているのですか？「範囲外の配列インデックス」エラーが何であるかは知っていますが、配列の場所が存在しない理由を理解できませんか?

  2. 最初の if 句は、配列がソートされているかどうかを確認します。コードをコンパイルすると、この句は最初の試行で満たされます(そもそも発生しないはずです)。そして、それがリターンA行で関数が終了しないのはなぜですか?

私が使っている本は John Bentley の 112 ページです。

4

3 に答える 3

0

この行で：int randomInt = randomGenerator.nextInt(U);

以下を使用して、L と U の間のランダムな int を取得する必要があります。

int randomInt = L + randomGenerator.nextInt(U - L);

また、 U を配列内の最大のインデックスにしたい場合は、それに渡す必要がありますintArray.length - 1

于 2013-11-01T08:42:15.487 に答える