java - Java String Quicksort は散発的に機能しますか?

Question

私はここで見た課題に取り組んでいますが、それらを見直した後でも、何が間違っているのかわかりません。文字列の配列をクイックソートする私のコードは機能しているようです-ほとんどの場合。しかし、何度も実行すると、間違った出力が得られることがあります。これを修正するためにどこを見ればよいかについてのアドバイスは大歓迎です..

import java.util.Random;
public class QuickSortStrings {

    static String[] strings;

    public static void main(String[] args) {

        strings = new String[args.length];

        for (int i = 0; i < args.length; i++) {
            strings[i] = args[i];
        }

        qsort(0, strings.length-1);

        System.out.print("The array, quicksorted: ");
        for (int i = 0; i < strings.length; i++)
        {
            System.out.print(strings[i] + " ");
        }
        System.out.println("\n");
    }

    static void qsort(int low, int high) {
        int i = low, j = high;

        // Get the pivot element
        Random r = new Random();
        int pivot = r.nextInt(high-low+1)+low;

        // Divide into two lists
        while (i <= j) {

          while (strings[i].compareTo(strings[pivot]) < 0) i++;

          while (strings[j].compareTo(strings[pivot]) > 0) j--;

          if (i <= j) {
            exchange(i, j);
            i++;
            j--;
          }
        }

        // Recursion
        if (low < j) qsort(low, j);
        if (i < high) qsort(i, high);
      }

    static void exchange(int i, int j) {
        String temp = strings[i];
        strings[i] = strings[j];
        strings[j] = temp;
    }
}

score 3 · Accepted Answer

解決策ではありませんがヒントです。私がそのような非決定論的な振る舞いをした場合、私は次のようにします:

ブール値を返す関数を追加して、配列がソートされているかどうかを確認します
反復ごとに呼び出し、失敗した場合 (機能しない入力データ配列を 1 つ見つけた場合) にのみ、問題のあるデータを出力またはシリアル化します。
次に、これらのデータを入力としてデバッガーを起動し、できればバグを追跡します。

score 0 · Accepted Answer

ソートの各反復は、ソート可能な範囲を縮小すると想定されています。基本的に、これは分割統治アルゴリズムです。

指定した範囲のpivot「中間」点を見つけます

問題は、をランダム化しているpivotため、並べ替えを実行するたびに、おそらく既に並べ替えたセクションを含むランダムなセクションを比較していることです...

だから、使用する代わりに...

int pivot = r.nextInt(high-low+1)+low;

あなたが使用している必要があります...

int pivot = low + (high - low) / 2;

例えば...

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class QuickSort {

    static String[] strings;

    public static void main(String[] args) {

        List<String> values = new ArrayList<>(26);
        for (int index = 0; index < 26; index++) {
            values.add(new String(new char[]{(char)(65 + index)}));
        }
        Collections.shuffle(values);

        strings = values.toArray(new String[values.size()]);
        System.out.println("Before");
        for (int i = 0; i < strings.length; i++) {
            System.out.print(strings[i] + " ");
        }
        System.out.println("");

        qsort(0, strings.length - 1);

        System.out.println("The array, quicksorted: ");
        for (int i = 0; i < strings.length; i++) {
            System.out.print(strings[i] + " ");
        }
        System.out.println("\n");
    }

    static void qsort(int low, int high) {
        int i = low, j = high;

        // Get the pivot element
        int pivot = low + (high - low) / 2;
        String value = strings[pivot];

        // Divide into two lists
        while (i <= j) {

            while (strings[i].compareTo(value) < 0) {
                i++;
            }

            while (strings[j].compareTo(value) > 0) {
                j--;
            }

            if (i <= j) {
                exchange(i, j);
                i++;
                j--;
            }
        }

        // Recursion
        if (low < j) {
            qsort(low, j);
        }
        if (i < high) {
            qsort(i, high);
        }
    }

    static void exchange(int i, int j) {
        String temp = strings[i];
        strings[i] = strings[j];
        strings[j] = temp;
    }

}

どちらが生成します...

Before
N S B A F Z X J Q K V C L R W E H Y M U G I D P T O 
The array, quicksorted: 
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 

Before
G U P Q D A W T R M E O X J S C I V Y F H L B N Z K 
The array, quicksorted: 
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 

Before
D Z C B Q O K W X F V G R S A U P T H Y I E N L M J 
The array, quicksorted: 
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 

Before
Q K H B W N J V C Y U O R P G I F D Z E L S A X M T 
The array, quicksorted: 
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 

Before
R V P G E S C A H W X I T D Z B K Q F M U Y L J N O 
The array, quicksorted: 
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 

Before
L O T E U D H N P J V I Q C X S Z W A R F K G Y B M 
The array, quicksorted: 
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 

Before
I E J F U X P K R Q L S C O Y W G A Z B V M D H N T 
The array, quicksorted: 
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 

Before
X L K T W E V J N Y G H O Q I M C P A R B F S U Z D 
The array, quicksorted: 
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 

Before
U X N T K Q S V P F W C G Y O L A B E H J R D M Z I 
The array, quicksorted: 
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 

Before
A J Z C M Y O Q F L K D P S X W N T I B H E R U V G 
The array, quicksorted: 
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

nb- の使用を強調しないでください。ListいくつかのランダムなStrings を生成しただけです ;)

java - Java String Quicksort は散発的に機能しますか?

2 に答える 2

Related

Reference