0

良い一日！ここに、クイックソートを行う Java プログラムがあります。ファイルを読み取り、その中の最初の 10,000 語をソートします。私は Thomas Cormen の Introduction to Algorithms, Second Ed の疑似コードに従いました。

import java.io.*;
import java.util.*;

public class SortingAnalysis {

    public static int partition(String[] A, int p, int r) {
        String x = A[r];
        int i = p-1;
        for (int j=p; j < r-1; j++) {
            int comparison = A[j].compareTo(x);
            if (comparison<=0) {
                i=i+1;
                A[i] = A[j];
            }       
        }
        A[i+1] = A[r];
        return i+1;
    }

    public static void quickSort(String[] a, int p, int r) {
        if (p < r) {
            int q = partition(a, p, r);
            quickSort(a, p, q-1);
            quickSort(a, q+1, r);
        }
    }

    public static void main(String[] args) {
        final int NO_OF_WORDS = 10000;
        try {
            Scanner file = new Scanner(new File(args[0]));
            String[] words = new String[NO_OF_WORDS];
            int i = 0;
            while(file.hasNext() && i < NO_OF_WORDS) {
                words[i] = file.next();
                i++;
            }
            long start = System.currentTimeMillis();
            quickSort(words, 0, words.length-1);
            long end = System.currentTimeMillis();
            System.out.println("Sorted Words: ");
            for(int j = 0; j < words.length; j++) {
                System.out.println(words[j]);
            }
            System.out.print("Running time: " + (end - start) + "ms");

        }
        catch(SecurityException securityException) {
            System.err.println("Error");
            System.exit(1);
        }
        catch(FileNotFoundException fileNotFoundException) {
            System.err.println("Error");
            System.exit(1);
        }
    }
}

しかし、コードを実行すると、
Exception in thread "main" java.lang.StackOverflowError at SortingAnalysis.partition and quickSort

サイズが大きい (つまり 10000) ためにエラーが発生したと思われるため、代わりに 100 に減らしたとコンソールに表示されます。ただし、ファイルから最初の 100 単語をソートするのではなく、100 番目の単語を 100 回表示します。
コードの修正を手伝ってください。私はJavaが初めてで、皆さんの助けが必要です。どうもありがとうございました！

編集:コードを編集しました。が 10000に達してもエラーは発生しなくなりました NO_OF_WORDS 。問題は、間違ったシーケンスを停止することです。

4

2 に答える 2

2

2 つの問題があります。

  • ループインは にpartition()実行されるはずj <= r - 1です。あなたは早く飛び出しています。

  • 要素を交換していません。次のコードを試してください。

    public static int partition(String[] A, int p, int r) {
   String x = A[r];
   int i = p - 1;
   for (int j = p; j <= r - 1; j++) {
       int comparison = A[j].compareTo(x);
       if (comparison <= 0) {
           i = i + 1;
           swap(A, i, j);
       }
   }
   swap(A, i + 1, r);
   return i + 1;
}

public static void swap(String[] a, int i, int j) {
   String temp = a[i];
   a[i] = a[j];
   a[j] = temp;    
}
于 2012-07-09T07:57:03.623 に答える
1

ウィキペディアのクイックソート アルゴを見ると、パーティション アルゴは次のようになります。

// left is the index of the leftmost element of the array
// right is the index of the rightmost element of the array (inclusive)
//   number of elements in subarray = right-left+1
function partition(array, 'left', 'right', 'pivotIndex')
  'pivotValue' := array['pivotIndex']
  swap array['pivotIndex'] and array['right']  // Move pivot to end
  'storeIndex' := 'left'
  for 'i' from 'left' to 'right' - 1  // left ≤ i < right
      if array['i'] < 'pivotValue'
          swap array['i'] and array['storeIndex']
          'storeIndex' := 'storeIndex' + 1
  swap array['storeIndex'] and array['right']  // Move pivot to its final place
  return 'storeIndex'

pivotIndexメソッドでは値を使用せず、インデックスpivotValueに基づいています。rightこのパラメーターをメソッドに追加する必要があります。

wiki アルゴリズムに従うと、次のようになります。

public static int partition(String[] A, int p, int r, int pivotIdx) {
    String x = A[pivotIdx];
    String tmp = A[pivotIdx];
    A[pivotIdx] = A[r];
    A[r]=tmp;
    int i = p;
    for (int j=p; j < r; j++) {
        int comparison = A[j].compareTo(x);
        if (comparison<=0) {
            tmp=A[i];
            A[i] = A[j];
            A[j]=tmp;
            i++;
        }       
    }
    tmp=A[i];
    A[i] = A[r];
    A[r]=tmp;
    return i;
}
于 2012-07-09T07:54:40.590 に答える