0

選択とバブルソートの両方を使用して乱数をソートするために必要な操作の数を比較するために、このプログラムを作成しました。ただし、これらの数値は同じように表示され続け、コードのどこが間違っているのかわかりません。

static int num_comps;   

public static void main(String[] args) 
{
    Random rnd = new Random();

    // max size of array
    // number of N inputs
    int array_size = 32768;
    int num_datasets = 12;

    // allocate array once to the max size
    int[] vals = new int[array_size];

    // temp array with allocated array to max size
    int[] tvals = new int[array_size];

    // array to hold operation counts
    int[] op_counts = new int[num_datasets];
    int[] op_counts2 = new int[num_datasets];

    // array to hold the size of each array
    //
    int[] arraySizes = new int[num_datasets];

    int i;
    int j;
    int sz;

    for (i = 0, sz = 16; i < num_datasets; i++, sz *= 2)
        arraySizes[i] = sz;

    for (int iter = 0; iter < num_datasets; iter++)
    {
        int curr_size = arraySizes[iter];

        // load array with random values
        //
        for (i = 0; i < curr_size; i++)
            vals[i] = rnd.nextInt(4999);

        for (i = 0; i < curr_size; i++)
            tvals[i] = vals[i];

        // run the bubble sort algorithm
        //
        num_comps = 0;
        bubbleSort(tvals, curr_size);
        op_counts[iter] = num_comps;
        //System.out.println("Num comps at " + iter + " is " + num_comps);

        // run the selection-sort algorithm
        num_comps = 0;
        selectionSort(tvals, curr_size);
        op_counts2[iter] = num_comps;
        //System.out.println("Num comps at " + iter + " is " + num_comps);
    }

    System.out.println("Operation Counts (N vs. op Count): ");
    for (int k = 0; k < num_datasets; k++)
        System.out.println(arraySizes[k] + "\t\t" + op_counts[k] + "\t\t" + op_counts2[k]);
}

static void bubbleSort(int vals[], int curr_size)
{
    int temp;
    for (int i = 0; i < curr_size - 1; i++)
    {
        for (int j = 0; j < curr_size - i - 1; j++)
        {
            // swap
            num_comps = num_comps + 1;
            if (vals[j+1] < vals[j])
            {
                temp = vals[j];
                vals[j] = vals[j+1];
                vals[j+1] = temp;
            }
        }
    }
}

static void selectionSort(int vals[], int curr_size)
{
    int temp;
    for(int i=0; i<curr_size - 1; i++)
     {
        for(int j=i+1; j<curr_size; j++)
        {
            num_comps = num_comps + 1;
            if(vals[i] > vals[j] )
            {
                temp = vals[j];
                vals[j] = vals[i];
                vals[i] = temp;
            }
        }
     }
}
4

1 に答える 1

2

選択ソートアルゴリズムは、リスト内の最小値を検索しません。その後、外側のループのインデックスと交換します。

次のようなことをする必要があります。

static void selectionSort(int vals[], int curr_size)
{
    int temp;
    for(int i=0; i<curr_size - 1; i++)
    {
        int lowest = i;
        for(int j=i+1; j<curr_size; j++)
        {
            num_comps = num_comps + 1;
            if(vals[lowest] > vals[j] )
            {
                lowest = j;
            }
        }

        // swap lowest with current index
        temp = vals[lowest];
        vals[lowest] = vals[i];
        vals[i] = temp;
     }
}

（もちろん、これはさらに最適化できます）このアルゴリズムの強みは、比較の量ではなく、このスワップの量です（少なくとも、これは私が思うに）。

あなたのバブルソートアルゴリズムは私には問題ないようです。

どちらも同じ2つのループを持っているため、現在の実装のカウントを比較すると、実際には同じ値になります。ただし、バブルソートを最適化して、早期に停止することができると思います（スワップが見つからなかった場合）。繰り返しますが、ソートアルゴリズムの強度は使用するアルゴリズムによって異なり、必ずしも最小量の比較ではありません。したがって、特定のタスクに適切なアルゴリズムを使用し、それによってタスク固有の高コストの操作を回避することが重要です。

于 2013-02-18T22:14:02.053 に答える