选择排序和冒泡排序之间的比较次数保持不变 [英] Number of Comparisons between selection sort and bubble sort keep coming up the same

问题描述

我已经编写了该程序来比较使用选择和冒泡排序对随机数进行排序所需的操作数.但是，这些数字保持不变，我无法弄清楚我的代码出了什么问题.

I have written this program to compare the number of operations needed to sort a random numbers using both selection and bubble sort. However, these numbers keep coming up the same and I can't figure out where my code went wrong.

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;
            }
        }
     }
}

推荐答案

您的选择排序算法不搜索列表中的最小值.然后将其与外部循环的索引交换.

Your selection sort algorithm does not search for the lowest value in the list. And swapping it afterwards with the index of the outer loop.

您应该执行以下操作:

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;
     }
}

(当然可以进一步优化) 这种算法的优势不是比较的数量，而是交换的数量(我想这是最少的).

(of course this can be optimized further) The strength of this algorithm is not the amount of of comparisons, but this amount of swaps (which is at a minimum, I suppose).

您的气泡排序算法对我来说似乎可以.

Your bubble sort algorithm seems ok to me.

两者都有相同的两个循环，因此比较当前实现的计数确实会得到相同的值.但是，我认为您可以优化气泡排序，以尽早停止(未找到任何交换时).同样，排序算法的强度取决于所使用的算法，并且不一定是最少量的比较.因此，针对您的特定任务使用正确的算法，从而规避特定于任务的高成本操作非常重要！

Both have the same two loops, so comparing the counts of the current implementations indeed result in the same values. But, I think you can optimize the bubble sort, to stop earlier (when no swaps were found). Again, the strength of sorting algorithms depends on the used ones, and are not necessarily the least amount of comparisons. So Using the correct algorithm for your specific task, and thereby circumventing the task-specific high cost operations, is important!

这篇关于选择排序和冒泡排序之间的比较次数保持不变的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！