10 000 000 Сортировка целочисленных массивов в Java

Question

Итак, я правильно написал код сортировки вставок, чтобы он успешно создавал массивы из 10, 1000, 100 000 и 1 000 000 целых чисел от 1 000 до 9 999 и прекрасно выполнял алгоритм сортировки вставок.Однако, когда я пытаюсь выполнить последний шаг из 10 000 000 целых чисел, массив создается, но код никогда не завершается полностью.Я дал ему достаточно времени для завершения, от 4 до 5 часов, но безрезультатно.У кого-нибудь есть идеи о том, что проблема может быть здесь?Имеет ли исполнитель проблемы, понимающие, что такое много целых чисел, или из-за чего может возникнуть проблема?Я включил копию алгоритма вставки, который я написал.

    public static void insertion(int[] a) {
    int n = a.length;

    for(int i = 1; i < n; i++) {
        int j = i -1;
        int temp = a[i];

        while(j > 0 && temp < a[j]) {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = temp;
    }
}

Answer 1

Кто-нибудь есть какие-либо идеи о том, что проблема может быть здесь?

Когда вы увеличиваете массив в 10 раз, вам придется ждать в 100 раз дольше, поскольку это алгоритм O (n ^ 2).

Имеет ли исполнитель проблемы, понимая, чтомного целых или из чего может возникнуть проблема?

Нет, ограничение составляет 2 ^ 31-1, и вы далеко от него.

Бег

interface A {
    static void main(String[] a) {
        for (int i = 25_000; i <= 10_000_000; i *= 2) {
            Random r = new Random();
            int[] arr = new int[i];
            for (int j = 0; j < i; j++)
                arr[j] = r.nextInt();
            long start = System.currentTimeMillis();
            insertion(arr);
            long time = System.currentTimeMillis() - start;
            System.out.printf("Insertion sort of %,d elements took %.3f seconds%n",
                    i, time / 1e3);
        }
    }

    public static void insertion(int[] a) {
        int n = a.length;

        for (int i = 1; i < n; i++) {
            int j = i - 1;
            int temp = a[i];

            while (j > 0 && temp < a[j]) {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = temp;
        }
    }
}

печать

Insertion sort of 25,000 elements took 0.049 seconds
Insertion sort of 50,000 elements took 0.245 seconds
Insertion sort of 100,000 elements took 1.198 seconds
Insertion sort of 200,000 elements took 4.343 seconds
Insertion sort of 400,000 elements took 19.212 seconds
Insertion sort of 800,000 elements took 71.297 seconds

Таким образом, мой компьютер может занять порядка 4 часов, но это может занять больше времени, поскольку больший набор данных не помещается в кэш-память третьего уровня, а скорее в основную память, которая работает медленнее.