时间戳

首页 > 解决方案 > 我的 BogoSort 程序可能有逻辑错误

java - 我的 BogoSort 程序可能有逻辑错误

问题描述

对于作业，我必须编写一些 Bogosort 代码，并凭经验确定程序的大 O 表示法。

但是，我不确定代码是否有效，因为即使它对 int 类型的 3 和 4 元素数组进行排序，我认为它不应该在 0 毫秒内完成。

反之，5个元素的耗时确实很长（15分钟内还没有成功案例），这对我来说表明程序可能有问题。由于没有抛出错误，我相信发现的任何问题都是逻辑错误。

我试过在程序上运行 IDE 调试器。用于 bogosort 的每种方法似乎都按预期工作，尽管我无法达到在使用调试器时正确排序数组的情况。

但是，通过更改数组的值使其已排序，我能够测试数组已排序的情况，并且代码已成功执行。

这似乎表明问题（如果有的话）与排序中的逻辑错误有关，排序方法在某种程度上永远无法找到正确的解决方案。

该文件如下所示，并已注释。

对程序的任何建议都必须与当前结构有关（不添加方法，不使用 ArrayLists），因为这是一项家庭作业。

public class BogoSort {

    public static void main(String[] args) {
        int[] myArray = {20, 142, 115, 120, 140};
        //sets start time
        long start = System.currentTimeMillis();
        bogoSort(myArray);
        //sets end time
        long end = System.currentTimeMillis();
        printArray(myArray);
        //print time (end time - start time)
        System.out.println((end - start) + "ms");
    }

    // Places the elements of a into sorted order.
    public static void bogoSort(int[] a) {
        while(!isSorted(a)){
            //calls the shuffle method if it's not sorted
            shuffle(a);
        }
    }
    // Returns true if a's elements are in sorted order.
    public static boolean isSorted(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            if (a[i] > a[i+1]) {
                //returns false if the number in this index is greater than 
                //the number in the next index aka not sorted 
                return false;
            }
        }       
        //else return true
        return true;
    }
    // Shuffles an array of ints by randomly swapping each
    // element with an element ahead of it in the array.
    public static void shuffle(int[] a){
        Random r = new Random();
        for(int i = a.length - 1;i > 0;i--){
            //random number between 0 and i
            int j = r.nextInt(i);
            //calls swap method  
            swap(a, i, j);
        }
    }
    // Swaps a[i] with a[j].
    public static void swap(int[] a, int i, int j) {
        //temp variable to hold value of a[i] for swap
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void printArray(int[] a)
    {
        for(int i = 0; i < a.length; i++)
        {
            System.out.println(a[i]);

        }
    }

}//end of BogoSort class

结果应如下所示：

20
115
120
140
142
???ms

？？？如果我正确理解bogosort 的 Big O 表示法，是程序运行时间的值，可能约为 720 毫秒。

目前，我还没有得到大小为 4 的数组的结果。

对 3 个或 4 个元素的数组进行排序所需的时间是 0 毫秒，这对我来说有点奇怪，我觉得 3 个元素应该是 24 毫秒，4 个元素应该是 120 毫秒。

3 或 4 元素数组的排序结果是数字按预期结果正确排序。

标签： java

解决方案

您的 shuffle 算法由于 off-by-1 错误而被破坏。如果您尝试使用int[] myArray = {2,1,3};，您会发现它也无法完成 3 个元素。

在处理随机性时，最好使用统计数据而不是目测，因为很难一眼就注意到这一点：

$ java BogoSort | head -n 100000 > file
$ sort file | uniq -c
33325 [1, 3, 2]
33315 [2, 1, 3]
33360 [3, 2, 1]

如您所见，您只能生成 6 种可能排列中的 3 种。

当您洗牌时，如您的评论所示，您将每个元素与数组中较早的一个元素交换。您还需要让元素保持原位。您可以通过将 1 添加到您选择的索引来做到这一点：

// Shuffles an array of ints by randomly swapping each
// element with an element ahead of it in the array **or leave it in place**.
public static void shuffle(int[] a){
    Random r = new Random();
    for(int i = a.length - 1;i > 0;i--){
        //random number between 0 and i
        int j = r.nextInt(i+1);   // <-- +1 here to select the current element
        //calls swap method
        swap(a, i, j);
    }
}

结果现在看起来更好（我操纵了程序，即使它已排序也能继续打印）：

$ sort file | uniq -c
16807 [1, 2, 3]
16579 [1, 3, 2]
16745 [2, 1, 3]
16697 [2, 3, 1]
16361 [3, 1, 2]
16811 [3, 2, 1]

事实上，它现在在 0-1 毫秒内完成。在 8 个数字上运行大约需要 10 毫秒，10 个数字需要大约 150 毫秒，这与预期的阶乘曲线一致。

推荐阅读