, измененный, чтобы быть гибридом в месте сортировки слиянием / сортировки вставки. Он рекурсивный, поэтому он также использует вспомогательное хранилище в стеке. Кроме того, это не «стабильный» вид.

й день ТАК сообщество,

Я студент CS, в настоящее время выполняю эксперимент, объединяющий MergeSort и InsertionSort. Понятно, что для определенного порога, S, InsertionSort будет иметь более быстрое время выполнения, чем MergeSort. Следовательно, путем объединения обоих алгоритмов сортировки, общее время выполнения будет оптимизировано.

Однако после многократного запуска эксперимента с использованием размера выборки 1000 и различных размеров S результаты эксперимента не дают однозначного ответа каждый раз. Вот картинка с лучшими полученными результатами (обратите внимание, что в половине случаев результат не так определен):

Теперь попробуем тот же код алгоритма с размером выборки 3500:

Наконец, попробуйте тот же код алгоритма с размером выборки 500 000 (обратите внимание, что ось Y находится в миллисекундах:

Хотя по логике Hybrid MergeSort будет быстрее, когда S <= 10, так как InsertionSort не имеет рекурсивных издержек. Однако результаты моего мини эксперимента говорят об обратном.

В настоящее время мне преподают Сложности Времени:

MergeSort: O (n log n)

сортировка вставки:

Лучший случай: θ (n)Худший случай: θ (n ^ 2)

Наконец, я нашел онлайн-источник:https://cs.stackexchange.com/questions/68179/combining-merge-sort-and-insertion-sort в котором говорится, что:

Гибридная сортировка слиянием:

Лучший вариант: θ (n + n log (n / x))В худшем случае: θ (nx + n log (n / x))

Я хотел бы спросить, есть ли результаты в сообществе CS, которые показываютокончательное доказательство того, что алгоритм гибридной слияния MergeSort будет работать лучше, чем обычный алгоритм слияния MergeSort ниже определенного порога S, и если да, то почему?

Огромное спасибо SO сообществу, это может быть тривиальный вопрос, но он действительно прояснит многие вопросы, которые у меня есть в настоящее время относительно сложности времени и прочего :)

Примечание: я использую Java для кодирования алгоритма, и время выполнения может зависеть от способа, которым java хранит данные в памяти.

Код на Java:

 public static int mergeSort2(int n, int m, int s, int[] arr){
        int mid = (n+m)/2, right=0, left=0;
        if(m-n<=s)
            return insertSort(arr,n,m);
        else
        {
            right = mergeSort2(n, mid,s, arr);
            left = mergeSort2(mid+1,m,s, arr);
            return right+left+merge(n,m,s,arr);
        }      
    }

    public static int insertSort(int[] arr, int n, int m){
        int temp, comp=0;
        for(int i=n+1; i<= m; i++){
            for(int j=i; j>n; j--){ 
                comp++;
                comparison2++;
                if(arr[j]<arr[j-1]){
                    temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
                else
                    break;
            }
        }
        return comp;
    }

    public static void shiftArr(int start, int m, int[] arr){
        for(int i=m; i>start; i--)
            arr[i] = arr[i-1];     
    }

public static int merge(int n, int m, int s, int[] arr){
        int comp=0;
        if(m-n<=s)
            return 0;
        int mid = (n+m)/2;
        int temp, i=n,  j=mid+1;
        while(i<=mid && j<=m)
        {
            comp++;
            comparison2++;


            if(arr[i] >= arr[j])
            {
                if(i==mid++&&j==m && (arr[i]==arr[j]))
                    break;
                temp = arr[j];
                shiftArr(i,j++,arr);
                arr[i] = temp;
                if(arr[i+1]==arr[i]){
                   i++;
                }
            }
            i++;


        }
        return comp;
    }
 Thomas Jungblut29 сент. 2017 г., 22:55
3500 элементов недостаточно велики, чтобы показать асимптотическое время выполнения. Также, пожалуйста, включите ваш код, Java позволяет легко создавать некорректные тесты.
 Benji Tan29 сент. 2017 г., 23:00
Привет @ThomasJungblut! Я включил код, но, к сожалению, я новичок в SO и не знаю, как создать скрипку .. в настоящее время пытаюсь получить результаты с размером выборки 500 000 :)
 Benji Tan29 сент. 2017 г., 22:55
Привет @ Tyler, да, сделаю, он говорит, что мне нужно подождать еще 20 минут, чтобы опубликовать его на бирже CS Stack :)
 D.W.30 сент. 2017 г., 03:27
Эй, @Tyler, пожалуйста, не поощряйте людей кросс-постить на нескольких сайтах SE.Каждое сообщество должно иметь честный ответ, не теряя никого времени, Спасибо!
 Tyler29 сент. 2017 г., 22:49
интересная работа! Я не буду говорить, если это хороший вопрос для SO, но я рекомендую также разместить его наОбмен компьютерными науками для большей наглядности

Ответы на вопрос(1)

Решение Вопроса

перемещает массив вместо слияния прогонов между исходным массивом и временным рабочим массивом и обратно.

Я проверил сортировки слиянием сверху вниз и снизу вверх, и обе из них занимают около 42 мс == 0,042 секунды для сортировки 500 000 32-битных целых чисел, в отличие от очевидных результатов на графике, которые в 1000 раз медленнее примерно на 42 секунды вместо 42 мс. Я также проверил с 10 000 000 целых чисел, и сортировка занимает чуть более 1 секунды.

В прошлом, используя C ++, я сравнивал восходящую сортировку слиянием с гибридной восходящей сортировкой слиянием / вставкой, и для 16 миллионов (2 ^ 24 == 16,777,216) 32-битных целых, гибридная сортировка была примерно на 8% быстрее с S == 16. S == 64 был немного медленнее, чем S == 16. Visual Studio std :: stable_sort - это вариант сортировки слиянием снизу вверх (временный массив равен 1/2 размера исходного массива) и сортировки вставкой, и использует S == 32.

Для небольших массивов сортировка вставкой выполняется быстрее, чем сортировка слиянием, комбинация локальности кэша и меньшее количество команд, необходимых для сортировки небольшого массива с сортировкой вставкой. Для псевдослучайных данных и S == 16–64 сортировка вставкой была примерно в два раза быстрее сортировки слиянием.

Относительное усиление уменьшается с увеличением размера массива. Учитывая влияние сортировки слиянием снизу вверх, при S == 16 оптимизируются только 4 прохода слияния. В моем тестовом примере с 2 ^ 24 == 16 777 216 элементов, это 4/24 = 1/6 ~ = 16,7% от числа проходов, что дает улучшение примерно на 8% (таким образом, сортировка вставкой примерно в два раза быстрее, чем слияние сортировка по этим 4 проходам). Общее время составило около 1,52 секунды для сортировки только слиянием и около 1,40 секунды для гибридной сортировки, что составляет 0,12 секунды для процесса, который занимает всего 1,52 секунды. Для сортировки слиянием сверху вниз, с S == 16, 4 наиболее глубоких уровня рекурсии будут оптимизированы.

Обновление - пример Java-кода для гибридной сортировки с вставкой / сортировки вставкой с O (n log (n)) сложностью по времени. (Примечание. Вспомогательное хранилище все еще используется в стеке из-за рекурсии.) Часть на месте выполняется на этапах слияния путем замены данных в области объединения на данные в области объединения. Это не стабильная сортировка (порядок одинаковых элементов не сохраняется из-за перестановки во время шагов слияния). Сортировка 500 000 целых чисел занимает около 1/8 секунды, поэтому я увеличил это значение до 16 миллионов (2 ^ 24 == 16777216) целых чисел, что занимает чуть более 4 секунд. Без сортировки вставки сортировка занимает около 4,524 секунды, а с сортировкой вставки с S == 64 сортировка занимает около 4,150 секунды, что составляет около 8,8% прироста. При практически одинаковом коде на C улучшение было меньше: с 2,88 секунды до 2,75 секунды, что примерно на 4,5% больше.

package msortih;
import java.util.Random;

public class msortih {

    static final int S = 64;    // use insertion sort if size <= S

    static void swap(int[] a, int i, int j) {
        int tmp = a[i]; a[i] = a[j]; a[j] = tmp;
    }

    // a[w:] = merged a[i:m]+a[j:n]
    // a[i:] = reordered a[w:]
    static void wmerge(int[] a, int i, int m, int j, int n, int w) {
        while (i < m && j < n)
            swap(a, w++, a[i] < a[j] ? i++ : j++);
        while (i < m)
            swap(a, w++, i++);
        while (j < n)
            swap(a, w++, j++);
    }  

    // a[w:]  = sorted    a[b:e]
    // a[b:e] = reordered a[w:]
    static void wsort(int[] a, int b, int e, int w) {
        int m;
        if (e - b > 1) {
            m = b + (e - b) / 2;
            imsort(a, b, m);
            imsort(a, m, e);
            wmerge(a, b, m, m, e, w);
        }
        else
            while (b < e)
                swap(a, b++, w++);
    }

    // inplace merge sort a[b:e]
    static void imsort(int[] a, int b, int e) {
        int m, n, w, x;
        int t;
        // if <= S elements, use insertion sort
        if (e - b <= S){
            for(n = b+1; n < e; n++){
               t = a[n];
               m = n-1;
                while(m >= b && a[m] > t){
                    a[m+1] = a[m];
                    m--;}
                a[m+1] = t;}
            return;
        }
        if (e - b > 1) {
            // split a[b:e]
            m = b + (e - b) / 2;
            w = b + e - m;
            // wsort -> a[w:e] = sorted    a[b:m]
            //          a[b:m] = reordered a[w:e]
            wsort(a, b, m, w);
            while (w - b > 2) {
                // split a[b:w], w = new mid point
                n = w;
                w = b + (n - b + 1) / 2;
                x = b + n - w;
                // wsort -> a[b:x] = sorted    a[w:n]
                //          a[w:n] = reordered a[b:x]
                wsort(a, w, n, b);
                // wmerge -> a[w:e] = merged    a[b:x]+a[n:e]
                //           a[b:x] = reordered a[w:n]
                wmerge(a, b, x, n, e, w);
            }
            // insert a[b:w] into a[b:e] using left shift
            for (n = w; n > b; --n) {
                t = a[n-1];
                for (m = n; m < e && a[m] < t; ++m)
                    a[m-1] = a[m];
                a[m-1] = t;
            }
        }
    }

    public static void main(String[] args) {
        int[] a = new int[16*1024*1024];
        Random r = new Random(0);
        for(int i = 0; i < a.length; i++)
            a[i] = r.nextInt();
        long bgn, end;
        bgn = System.currentTimeMillis();
        imsort(a, 0, a.length);
        end = System.currentTimeMillis();
        for(int i = 1; i < a.length; i++){
            if(a[i-1] > a[i]){
                System.out.println("failed");
                break;
            }
        }
        System.out.println("milliseconds " + (end-bgn));
    }
}
 Benji Tan30 сент. 2017 г., 09:56
Будет включать это в мой вывод, когда я представлю отчет :) Да из-за меньшего количества рекурсий при меньших размерах, следовательно, уменьшенная часть log2 (н / с)! Однако проблема, с которой я столкнулся сейчас, состоит в том, чтобы дать заключение о том, будет ли эта версия mergesort vs hybridsort (со смещением) сокращать время выполнения. Теоретически, гибридная сортировка должна все же быть быстрее, чем сортировка слиянием, однако смещение может также занимать время (так как смещение выполняется только во время вставки сортировочной части гибридной сортировки) ...
 rcgldr30 сент. 2017 г., 11:13
@BenjiTan - Вы можете взглянуть наэтот ответ для примера на месте сортировки слияния. Мне неясно, должны ли сортировки слиянием и гибридной сортировки сравнивать оптимизированные сортировки с заданными ограничениями, или нужно сравнить код примера в вопросе. Сортировка вставки может быть улучшена с помощью temp = ... перед циклом для смещения, а затем ... = temp после цикла для смещения.
 rcgldr30 сент. 2017 г., 09:25
@BenjiTan - пример кода в вопросе использует вспомогательное хранилище в стеке, кадры стека log2 (н / с) из-за рекурсии. Слияние снизу вверх позволит избежать этого.
 Benji Tan30 сент. 2017 г., 07:52
Здравствуй! Спасибо за разъяснения. Алгоритм, которому меня научили, пытается неявно решить проблему сложности пространства, не используя вспомогательное хранилище. Я тоже это заметил, что отличает алгоритм от исходного слияния. Возможно, поэтому мне не удалось воспроизвести результаты. Однако эксперимент, который я выполняю, «требует» использования метода смещения, поэтому мои результаты отличаются от стандартной гибридной сортировки. Еще раз спасибо за помощь!
 rcgldr02 окт. 2017 г., 06:02
@BenjiTan - я обновил свой ответ, чтобы показать пример алгоритма сортировки слиянием на месте изэтот ответ , измененный, чтобы быть гибридом в месте сортировки слиянием / сортировки вставки. Он рекурсивный, поэтому он также использует вспомогательное хранилище в стеке. Кроме того, это не «стабильный» вид.

Ваш ответ на вопрос