Разделяй и властвуй алгоритм пузырьковой сортировки

Question

В этом семестре мы узнали о Разделяй и властвуй , в котором проблема делится на подзадачи, а затем решается так же, как в Сортировке слиянием или Быстрой сортировке.

Хотя я не публикую этот вопрос Чтобы мои задачи были решены вами, наш профессор дал нам задание реализовать Bubble Sort в качестве алгоритма «разделяй и властвуй». Теперь я сижу на своем ноутбуке, несколько дней ломая голову над тем, как Bubble Sort может быть алгоритмом «разделяй и властвуй».

Если я попытаюсь реализовать Bubble Sort , так как делить и завоевывать массив необходимо разделить, когда я делю массив на его последний элемент, а затем объединяю его обратно в отсортированную форму, алгоритм просто становится Merge Sort.
Если я реализую его путем рекурсивного вызова bubbleSort (array, size-1), алгоритм становится Reduce and Conquer .

У меня вопрос " Как можно реализовать сортировку пузырьков как алгоритм «разделяй и властвуй»?"

Answer 1

Предположим, вы пишете bubblesort функцию, которая позволяет вам сортировать часть массива:

bubblesort(arr, start, end)
{
    // sorts the items from arr[start] to arr[end]
}

Так что, если у вас есть массив [1,7,4,9,6,3,2,5] и он называется bubblesort(arr, 0, 3), результирующий массив будет [1,4,7,9,6,3,2,5].

А теперь представьте, что произойдет, если вы сделаете эти звонки:

bubblesort(arr, 0, 1);
bubblesort(arr, 2, 3);
bubblesort(arr, 4, 5);
bubblesort(arr, 6, 7);

Затем

bubblesort(arr, 1, 3);
bubblesort(arr, 4, 7);

И, наконец:

bubblesort(arr, 0, 7);

Это тот же шаблон вызова, что и сортировкой слиянием, но это определенно не сортировка слиянием.