54668


Arraysクラスをimportせずに自身でソートアルゴリズムを実装する課題です。  
配列の要素数によっておこなうソートの方法を変更したいのです。  
(a)要素数1-6:基準値不要のインサーションソート ←実装OK  
(b)要素数7:クイックソート(基準値:配列の真ん中の値) ←実装OK  
(c)要素数8-40:クイックソート(基準値:配列の先頭，真ん中，末尾の値の中から２番目  
に大きい値) ←今ここ！悩んでいる！  
(d)要素数41-:クイックソート(基準値:配列を８等分した位置にある９つの値を選び，４～６番目に大きい値のどれか) ←まだ手つけていない

今エラーが出て、うまくいかなくて悩んでいるところが(c)です。  
この(c)が配列の値が1の位のみ({3,5,2,6,8,9,4,1}みたいなやつ)のときはソートが完了するのですが、それ以外の配列だとエラーが出ます。  
ちなみにエラーがでるのは2週目(再帰1週目)で、insertionSort(b);とquickSort2(a, i, toIndex);の部分です。  
1週目はうまくいくのです。しかし配列を2グループわけた2週目(再帰1週目)からなにかがうまくいってないのだと思います。

エラー内容:無限ループに陥っています  
試しに quickSort2(a, fromIndex, j);の後ろに  
System.out.println(j);をつけてみると  
2  
2  
2  
2  
2  
2  
.... という無限ループが起こりました。  
Exception in thread "main" java.lang.StackOverflowError  
at lesson02.ArraySort.quickSort2(ArraySort.java:72)  
at lesson02.ArraySort.quickSort2(ArraySort.java:85)  
at lesson02.ArraySort.quickSort2(ArraySort.java:85)  
at lesson02.ArraySort.quickSort2(ArraySort.java:85)  
at lesson02.ArraySort.quickSort2(ArraySort.java:85)  
at lesson02.ArraySort.quickSort2(ArraySort.java:85)  
at lesson02.ArraySort.quickSort2(ArraySort.java:85)  
at lesson02.ArraySort.quickSort2(ArraySort.java:85)  
at lesson02.ArraySort.quickSort2(ArraySort.java:85)  
at lesson02.ArraySort.quickSort2(ArraySort.java:85)  
at lesson02.ArraySort.quickSort2(ArraySort.java:85)  
at lesson02.ArraySort.quickSort2(ArraySort.java:85)  
at lesson02.ArraySort.quickSort2(ArraySort.java:85)  
at lesson02.ArraySort.quickSort2(ArraySort.java:85)  
at lesson02.ArraySort.quickSort2(ArraySort.java:85)  
at lesson02.ArraySort.quickSort2(ArraySort.java:85)  
at lesson02.ArraySort.quickSort2(ArraySort.java:85)  
at lesson02.ArraySort.quickSort2(ArraySort.java:85)  
at lesson02.ArraySort.quickSort2(ArraySort.java:85)  
at lesson02.ArraySort.quickSort2(ArraySort.java:85)  
at lesson02.ArraySort.quickSort2(ArraySort.java:85)  
at lesson02.ArraySort.quickSort2(ArraySort.java:85)  
.....

[code]

    package lesson02;
    import java.util.Arrays;
    
    public class ArraySort {
    
        //要素数で割った値(=gap)を左端から順にたしていく
        //2晩目に大きい値の添え字を戻すようにする
    
        public void sort(int[] a){
    
            int leaf = leafValue(a); //要素数の範囲を決める値
            switch(leaf){
    
    
            case 1:
                System.out.println("(a)インサーションソートを行います.");
                insertionSort(a);
                break;
    
            case 2:
                System.out.println("(b)でクイックソートを行います.");
                quickSort1(a,0, a.length - 1);
                break;
    
            case 3:
                System.out.println("(c)でクイックソートを行います.");
                quickSort2(a,0, a.length - 1);
                break;
    
            case 4:
                System.out.println("(d)でクイックソートを行います.");
                quickSort3(a,0, a.length - 1);
                break;
    
            default: System.out.println("やり直してください.");
            }
        }
    
        public static void insertionSort(int[] a){
            for(int i=1;i<a.length;i++){
                int j;
                int tmp = a[i];
                for(j=i;j>0 && a[j-1]>tmp;j--){
                    a[j] = a[j-1];
                }
                a[j] = tmp;
            }
        }
    
        public static void quickSort1(int[] a, int fromIndex, int toIndex){
            int x = a[(fromIndex + toIndex) / 2]; // 基準値
            int i = fromIndex; // 基準値より大きい値を探すカーソル
            int j = toIndex; // 基準値より小さい値を探すカーソル
    
            while (i <= j) { // カーソルの位置関係が逆転しない限りループする
                while (a[i] < x)
                    i++;
                while (a[j] > x)
                    j--;
                if (i <= j)
                    swap(a, i++, j--);
            }
            if (fromIndex < j)
                quickSort1(a, fromIndex, j); // 左側の再帰的なソート
            if (i < toIndex)
                quickSort1(a, i, toIndex); // 右側の再帰的なソート
        }   
    
        //うまくいかない、悩んでいるところ！！！！！！
        //配列の先頭，真ん中，末尾の値の中から２番目に大きい値を基準値にする
        public static void quickSort2(int[] a, int fromIndex, int toIndex){
            int x = a[(fromIndex + toIndex) / 2]; 
            int i = fromIndex; 
            int j = toIndex; 
            int[] b = new int[] {x,i,j};
            insertionSort(b);
            x = b[1];
            while (i <= j) { // カーソルの位置関係が逆転しない限りループする
                while (a[i] < x)
                    i++;
                while (a[j] > x)
                    j--;
                if (i <= j)
                    swap(a, i++, j--);
            }
            if (fromIndex < j)
                quickSort2(a, fromIndex, j); // 左側の再帰的なソート
            if (i < toIndex)
                quickSort2(a, i, toIndex); // 右側の再帰的なソート
        }
    
        public static void quickSort3(int[] a, int fromIndex, int toIndex){
            //要素数で割った値(=gap)を左端から順にたしていく
            //2晩目に大きい値の添え字を戻すようにする
            //未実装(先quickSort2おわってからやる)
        }
    
        //スワップするメソッド
        public static void swap(int[] a, int idx1, int idx2) {
            int tmp = a[idx1];
            a[idx1] = a[idx2];
            a[idx2] = tmp;
        }
    
        //要素数を調べるメソッド
        public static int leafValue(int[] a){
            int leaf = 0; //判定値
            int n = a.length;//要素数
            if(1<=n&&n<=6){
                leaf = 1;
                System.out.println("要素数は1~6です.");
            }
            if(n==7){
                leaf = 2;
                System.out.println("要素数は7です.");
            }
            if(8<=n&&n<=40){
                leaf =3;
                System.out.println("要素数は8~40です.");
            }
            if(41<=n){
                leaf = 4;
                System.out.println("要素数は41以上です.");
            }else{
            }
            return leaf;
        }
    
        //mainメソッド
        public static void main(String[] args) {
            ArraySort array = new ArraySort();
            int[] a = new int[] {8,5,11,2,15,24,1,19};
            System.out.printf("ソート前: %s\n", Arrays.toString(a));
            array.sort(a);
            System.out.printf("ソート後: %s\n", Arrays.toString(a));
        }
    }
    
[/code]


CC BY-SA 4.0
2019-05-03T01:53:34.743
54665
2019-05-03T02:27:03.643
2019-05-03T02:27:03.643
question
java
ソートアルゴリズムの実装


問題なのはこの行ですね。

[code]

    int[] b = new int[] {x,i,j};
    
[/code]

ここで`x`は配列の要素の値であるのに対し、`i`と`j`はインデックスですから、まったく異質のものを比較していることになります。

で、配列のソート範囲以外の値が境界値として選ばれてしまうと、コードが暗黙のうちに前提としていることが壊れて、記載されたような事象が起こります。

さっきの行はこうでしょうね。

[code]

    int[] b = new int[] {x,a[i],a[j]};
    
[/code]

配列`b`に入れるのは、配列中の要素からピックアップしたものでないといけません。

* * *

本題とは直接関係はありませんが、

[code]

    swap(a, i++, j--);
    
[/code]

のように副作用のある式を実引数に使うくせは改めた方が良いでしょうね。将来もっと複雑なコードを扱うようになった時に、評価順序の問題で見つけにくいバグを引き起こすことがあります。(他にもいろいろあるんですが、本題と離れすぎるんでこの辺で。)


CC BY-SA 4.0
2019-05-03T02:26:52.417
54668
2019-05-03T02:26:52.417
13972
54665
answer