0

いくつかのソートアルゴリズムを練習しているだけです。再帰マージソートを実装しようとしましたが、再帰呼び出しごとに新しいピボットを取得することに問題があるようです。

私のコードは機能しているように感じます...しかし、ArrayListをデータ構造として使用するのは初めてで、配列の経験しかありません。動的サイズの配列が必要だったので、ArrayList を使用しています。

オーバーフローするまで、 pivot = 1 を吐き出し続けます。

pivot: 1
pivot: 1
pivot: 1
pivot: 1
pivot: 1
...
Exception in thread "main" java.lang.StackOverflowError

コード：

      import java.util.*;

public class Sorts{
    static Sorts run;               
    List<Integer> initialList = new ArrayList<Integer>();

    public Sorts() {

        //List<Integer> initialList = new ArrayList<Integer>();


        initialList.add(1);
        initialList.add(4);
        initialList.add(8);
        initialList.add(2);
        initialList.add(3);
        initialList.add(7);
        initialList.add(9);


        System.out.print("List of values: (");
        for (int value: initialList) {
            System.out.print(value);
        }
        System.out.println(")");

        //output sorted array
        System.out.println("Sorted list: " + mergeSort(initialList));                                                          
    }

    public List<Integer> mergeSort(List<Integer> list) {                               
        if (list.size() <= 1) {
            return list;
        }

        //after each recursion, generate two new sub lists
        List<Integer> left = new ArrayList<Integer>();
        List<Integer> right = new ArrayList<Integer>(); 

        //generate new pivot for each new list
        int middle = list.size()/2;
        System.out.println("middle: " + middle);

        int i = 0;
        for (int x: list) {
            if (i < middle) {
                left.add(x);
            }
            else {
                right.add(x);
            }
            i++;
        }

        //call mergeSort, passing in each new sublist (left, right)
      left = mergeSort(left);
      right = mergeSort(right);

       return mergeLists(left, right);
     }

    public List<Integer> mergeLists (List<Integer> left, List<Integer> right) {
        List<Integer> sortedList = new ArrayList<Integer>();
        int i = 0;
        while (left.size() > 0 || right.size() > 0) {
            if (left.size() > 0 && right.size() > 0) {
                if (left.get(i) <= right.get(i)) {
                    sortedList.add(left.get(i));
                }
                else {
                    sortedList.add(right.get(i));
                }
            }
            else if (left.size() > 0) {
                sortedList.add(left.get(i));
            }
            else if (right.size() > 0) {
                sortedList.add(right.get(i));
            }
        }

        for (int value : sortedList) {
            System.out.println(value);
        }
        return sortedList;
    }

    public static void main(String []args){
        run = new Sorts();
    }
}

何かご意見は？ArrayList の使い方が間違っていますか?

ありがとう！

4

2 に答える 2

2

http://en.wikipedia.org/wiki/Merge_sortをご覧ください

ピボットと比較する必要はありません。実装しているパーティションソートではありません。このように、リストを2つに分割するだけです。

left = list.sublist(0, pivot);
right = list.sublist(pivot, list.length())
于 2013-03-22T06:01:43.850 に答える
2

問題は、リストを間違った方法で分割していることです。

for (int i: initialList) {
    if (i < pivot) {
        left.add(i);
    }
    else {
        right.add(i);
    }
}

iは の要素であり、要素initialListのインデックスではありません。これを次のように変更します。

int i = 0;
for (int x: initialList) {
    if (i < pivot) {
        left.add(x);
    }
    else {
        right.add(x);
    }
    i++;
}

反対票を投じた人のために：私はこれをテストして動作しました:)。

また、mergeアルゴリズムに問題があります。要素を並べ替えながら両方のリストをマージする必要がありますが、左の値を挿入してから右の値を挿入するだけです (ただし、テスト目的である可能性があります)。

編集に基づいて、ピボットを取得するときに新しい問題が発生しました。

int pivot = list.get(list.size()/2);

これは、元のコードで投稿したとおりです。

int pivot = initialList.size()/2;

はQuickSort で使用され、MergeSortpivotではor を使用middleするだけなので、人々は奇妙なアドバイスを言うかもしれないことに注意してください。mid

于 2013-03-22T05:55:43.547 に答える