4

このコードは、ファイルから多数のケースと配列のサイズを読み取り、配列を埋めて送信し、マージ ソートします。
問題は、私が取得index out of boundsし続け、それが私を殺していることです...

私のデバッガーは、Eclipse での動作を停止しました。

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class mergesort {

    public static void mergeSort(int[] array, int first, int last){
        int mid;
        if (first<last){
            mid = (last + first)/2;
            mergeSort(array, first, mid);
            mergeSort(array, mid+1, last);
            merge(array, first, last);
        }
    }

    public static void merge(int[] array, int first, int last){
        int mid = (last-first)/2;
        int[] temp = new int[(last-first)];
        int a1 = first, a2 = mid + 1, current = 0;
        while (a1 <=mid && a2<=last){
            if (array[a1] <= array[a2])
                temp[current++] = array[a1++];
            else
                temp[current++] = array[a2++];
        }
        for (int i = a1; i<=mid; i++)
            temp[current++] = array[i];
        for (int i = a2; i<=last; i++)
            temp[current++] = array[i];
        for (int i =0; i<temp.length; i++)
            array[first+i] = temp[i];
    }

    public static void main(String[] args) throws FileNotFoundException {
        File file = new File("sort.in");
        Scanner scan = new Scanner(file);
        int n1 = scan.nextInt();
        for (int i = 0; i<n1; i++){
            int[] array =new int[scan.nextInt()];
            for (int j = 0; j<array.length; j++){
                array[j] = scan.nextInt(); 
            }
            mergeSort(array, 0, (array.length)-1);
            for (int j = 0; j<array.length; j++){
                System.out.println(array[j]); 
            }
        }
    }
}
4

2 に答える 2

1

まず、temp配列が 1 要素短すぎます。

int[] temp = new int[(last-first)];

lastとの両方firstが含まれているため、上記は次のようになります。

int[] temp = new int[last - first + 1];
于 2013-02-27T17:54:31.870 に答える
1

プログラムのmerge一部には、最初にいくつかのバグがあります (NPE が示したものは含まれません)。

int mid = (last-first)/2;

次のようにする必要があります。

int mid = (last+first)/2;

次に、最後の 3 つの for ループは関係なく実行されますが、a1/a2 の残りの部分でのみ実行する必要があります。

私は少し違った方法で実装しました - 2番目のバグを説明するのに役立つかもしれません:

public static void mergeSort(int[] arr, int start, int end){
    if(start == end) return;
    // now the recursive calls:
    // divide the arr:
    int middle = (end+start)/2;
    mergeSort(arr, start, middle);
    mergeSort(arr, middle+1, end);
    // now merge (conquer)
    merge(arr, start, end, middle);
}

private static void merge(int[] arr, int start, int end, int middle) {
    int[] sorted = new int[end-start+1];        
    for(int i=start,j=middle+1,index=0; index < sorted.length;){
        if(j<=end && arr[i] > arr[j]){
            sorted[index] = arr[j];
            j++; index++;
        }
        else if (i<=middle){
            sorted[index] = arr[i];
            i++; index++;
        }
        else{
            sorted[index] = arr[j];
            j++; index++;
        }
    }
    // now copy "sorted" to original array
    for(int i=start,j=0; i<=end; i++,j++){
        arr[i] = sorted[j];
    }
}

public static void main(String...args){
    int[] arr = {4,2,9,6,2,8,1,9,10,15,12,11};
    mergeSort(arr, 0, arr.length - 1);
    for(int i=0; i<arr.length; i++){
        System.out.print(arr[i]+" ");
    }
}
于 2013-08-06T05:15:51.893 に答える