1

Java (コンソール アプリ) を使用して単純なバブル ソート アルゴリズムを実装しました。これは私の ArrayBub クラスです

public class ArrayBub {
private int[] _numbersArray;

// Constructor of class
public ArrayBub(int[] numbersArray) {
    _numbersArray = numbersArray;
}

public void BubbleSort() {
    long startTime = System.currentTimeMillis();
    System.out.println("Bubble sort - sort " + _numbersArray.length + " numbers in array (random order)");
    System.out.println("Initial array: " + Arrays.toString(_numbersArray));
    int i, j, temp;
    int n = _numbersArray.length;

    for (i = 0; i < n - 1; i++) {
        for (j = 1; j < n - i; j++) {
            if (_numbersArray[j - 1] > _numbersArray[j]) {
                temp = _numbersArray[j - 1];
                _numbersArray[j - 1] = _numbersArray[j];
                _numbersArray[j] = temp;
            }
        }
    }

    System.out.println("Final array: " + Arrays.toString(_numbersArray));
    System.out.println("Number of iterations: " + (i + 1));
    long endTime = System.currentTimeMillis();
    long executionTime = endTime - startTime;
    System.out.println("Execution time (in milliseconds): " + executionTime);
    System.out.println("-----------------------------------------------------------------------------");
}

次に、ランダムな整数で配列を作成するヘルパークラスがあります

public class ArrayGenerator {
public int[] GenerateRandomArray(int numberOfDigits) {
    ArrayList<Integer> list = new ArrayList<Integer>();
    int[] array = new int[numberOfDigits];
    long seed = System.nanoTime();
    int i;

    for (i = 1; i <= numberOfDigits; i++) {
        list.add(i);
    }

    Collections.shuffle(list, new Random(seed));

    for (i = 0; i <= list.size() - 1; i++) {
        array[i] = list.get(i).intValue();
    }

    return array;
}

最後に、メイン メソッドで ArrayBub クラスを呼び出します。

new ArrayBub(new ArrayGenerator().GenerateRandomArray(10)).BubbleSort();

ここに奇妙な問題があります:小さな配列を使用すると-10個のアイテムとしましょう-結果は期待どおりに見えます

バブル ソート - 配列内の 10 個の数字を並べ替える (ランダムな順序)

初期配列: [4, 5, 1, 9, 10, 6, 2, 8, 3, 7]

最終配列: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

反復回数: 10

実行時間 (ミリ秒): 1

しかし、非常に多数の整数 (50000 としましょう) に対してまったく同じコードを実行すると、結果は非常に奇妙になります。これはコンソールに表示されるものです

最終配列: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24、25、26……]

反復回数: 50000

実行時間 (ミリ秒): 4995

最終配列: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24、25、26……]

初期配列: [39500, 13400, 48276, 11997, 25616, ....]

では、なぜこれが起こって、結果が台無しになるのでしょうか?

4

0 に答える 0