1

並べ替えアルゴリズムの Merge Sort と Selection Sort の操作数を比較したいのですが、どの操作を数えてどれを数えないかを判断するのに問題があります。

これが私の実装です。正しい方法で選択ソートの操作を数えていると思いますが、マージソートについては知りません:

選択ソート:

public class SelectionSort {
private int exchanges, comparisons;

public void selectionSort(int[] x) {    
    for (int i=0; i<x.length-1; i++) {
        for (int j=i+1; j<x.length; j++) {
            if (x[i] > x[j]) 
            {
                //... Exchange elements
                int temp = x[i];
                x[i] = x[j];
                x[j] = temp;
                exchanges++;
            }
            comparisons++;
        }
    }
    System.out.println("SelSort_Exchanges: "+exchanges);
    System.out.println("SelSort_Comparisons: "+comparisons);
    System.out.println("SelSort_Operations: "+(exchanges+comparisons));
}
}

10 int の配列を入れると、次のようになります。

SelSort_Comparisons: 45
SelSort_Exchanges: 27
SelSort_Operations: 72

私には正しいように思えますが、今はマージソートの場合:

public class Mergesort {
private int[] numbers;
private int[] helper;

private int number;
private int comparisons, exchanges;

public void sort(int[] values) {
    this.numbers = values;
    number = values.length;
    this.helper = new int[number];
    mergesort(0, number - 1);
    System.out.println("MerSort_Comparisons "+comparisons);
    System.out.println("MerSort_Exchanges "+exchanges);
    System.out.println("MerSort_Operations "+(comparisons+exchanges));
    System.out.println();
}

private void mergesort(int low, int high) {
    // Check if low is smaller then high, if not then the array is sorted
    if (low < high) 
    {
        // Get the index of the element which is in the middle
        int middle = (low + high) / 2;
        // Sort the left side of the array
        mergesort(low, middle);
        // Sort the right side of the array
        mergesort(middle + 1, high);
        // Combine them both
        merge(low, middle, high);
    }
}

private void merge(int low, int middle, int high) {

    // Copy both parts into the helper array
    for (int i = low; i <= high; i++) {
        helper[i] = numbers[i];
        exchanges++;
    }
    int i = low;
    int j = middle + 1;
    int k = low;
    // Copy the smallest values from either the left or the right side back
    // to the original array
    while (i <= middle && j <= high) {
        if (helper[i] <= helper[j]) {
            numbers[k] = helper[i];
            i++;
            exchanges++;
        } else {
            numbers[k] = helper[j];
            j++;
            exchanges++;
        }
        k++;
        comparisons++;

    }
    // Copy the rest of the left side of the array into the target array
    while (i <= middle) {
        numbers[k] = helper[i];
        exchanges++;
        k++;
        i++;
    }
}   
}

今私は得る

MerSort_Comparisons 22
MerSort_Exchanges 61
MerSort_Operations 83

その結果ですが、それが正しいかどうかはわかりません。比較の結果は私には正しいように思えますが、たとえば 20 の配列を取ると、もう正しくないように見えます。

誰かがこれを手伝ってくれて、比較と交換の増分を正確にどこに置く必要があるか教えてもらえますか?

前もって感謝します！:)

4

1 に答える 1

1

最も簡単な方法は、2 つのメソッドを作成するCompareことSwapです。どのような並べ替えアルゴリズムを実装しても、これらのメソッドを使用して配列とのみやり取りする必要があります。

また、このページは、さまざまな並べ替えアルゴリズムを視覚的に分析するのに役立ちます。

于 2012-06-19T11:09:16.997 に答える