Quicksort / Insertion Сортировать комбо медленнее, чем просто Quicksort?

Question

Я запускаю Quicksort 10 раз и получаю среднее время.Я делаю то же самое для комбинации сортировки Qicksort / Insertion, и она кажется медленнее, чем просто быстрая сортировка.

Вот часть кода, где я называю InsertionSort

public static <T extends Comparable<? super T>> void OptQSort2 (T[] data, int min, int max) {
        int indexofpartition;
        if(max - min > 0) {
            if( (max - min) <= 10) {
                // Use InsertionSort now
                InsertionSort.sort(data);
                return;
            } else {
                indexofpartition = findPartition(data, min, max);

                OptQSort2(data, min, indexofpartition - 1);

                OptQSort2(data, indexofpartition + 1, max);
            }
        }

}

И обычнуюБыстрая сортировка аналогична приведенному выше фрагменту, но без условия if, вызывающего InsertionSort.

FindPartition выглядит следующим образом:

public static <T extends Comparable<? super T>> int findPartition(T[] data, int min, int max) {
    int left, right;
    T temp, partitionelement;
    int middle = (min + max)/2;

    partitionelement = data[middle];
    left = min;
    right = max;

    while(left < right) {
        while(data[left].compareTo(partitionelement) <= 0 && left < right)
            left++;

        while(data[right].compareTo(partitionelement) > 0)
            right--;

        if(left < right) {
            temp = data[left];
            data[left] = data[right];
            data[right] = temp;
        }
    }

Среднее время только для Quicksort и OptSort2 (в котором используетсясортировка вставки)

Sorted using QuickSort in: 3858841
Sorted using OptQSort2 in: 34359610

Есть идеи почему?Имеет ли значение размер последовательности?Я использую массив из 1000 элементов Integer [] для этого

Answer 1

В OptQSort2 для небольших разделов у вас есть следующий вызов функции:

InsertionSort.sort(data);

Предполагается ли это для вставки сортировки малого раздела?Похоже, вы вставляете сортировку всего массива .Разве вы не должны передавать индексы min и max в InsertionSort?

Другой вариант - просто не работать на небольших разделах во время OptQSort2.Затем выполните один InsertionSort проход по всему массиву после того, как OptQSort2 выполнит свою работу.

Answer 2

Первый подозреваемый, очевидно, ваш метод сортировки вставкой.Например, действительно ли он сортируется?

Вам также потребуется более 10 раз протестировать его, чтобы прогреть JVM.А также проверить их в обоих порядках, чтобы один не извлек выгоду из разогрева, выполненного другим.Я бы предложил 100 или 1000 тестов.И все они тоже должны быть в одном наборе данных.

Answer 3

Вам понадобится намного больший целочисленный массив, чтобы тест был релевантным. На данный момент, вероятно, проверка условия if замедляет ваш алгоритм в случае QS + IS.

Проверка на большое количество чисел и переключение на IS, когда размер данных достаточен для размещения в кэше L1, т. Е. 32-64 КБ.

Answer 4

Вы не должны вызывать InsertionSort каждый раз, когда у вас есть подмассив не более 10 элементов.Ничего не делать:

public static <T extends Comparable<? super T>> void OptQSort2 (T[] data, int min, int max) {
    int indexofpartition;
        if( (max - min) > 10) {
            indexofpartition = findPartition(data, min, max);

            OptQSort2(data, min, indexofpartition - 1);

            OptQSort2(data, indexofpartition + 1, max);
        }

}

Когда вы закончите, вызовите InsertionSort для всего массива.