Алгоритм Форда–Джонсона CPP09 - javascript.org.ua

математика складна:(

Алгоритм сортування Ford-Johnson Merge-Insertion, розроблений у 1959 році Лестером Фордом та Сельмером Джонсоном, відомий тим, що мінімізує кількість порівнянь, необхідних під час сортування. На відміну від інших алгоритмів сортування, які орієнтовані на швидкість та легкість реалізації, алгоритм Ford-Johnson зосереджений на зменшенні кількості порівнянь, встановлюючи стандарт у цій галузі досліджень.

У цій статті ми розглянемо, як реалізувати цей алгоритм у C++ крок за кроком. Але перед тим давайте теоретично розберемося, що це за алгоритм.

Наприклад, розглянемо сортування списку чисел. Алгоритм починається з розбиття списку на менші підсписки і сортування цих підсписків за допомогою сортування вставками. Потім ці відсортовані підсписки об'єднуються таким чином, щоб мінімізувати кількість порівнянь.
Уважно вибираючи елементи для порівняння та злиття, алгоритм гарантує, що загальна кількість порівнянь зберігається на мінімальному рівні, що робить його дуже ефективним для певних типів даних.

Кроки алгоритму сортування Ford-Johnson Merge-Insertion:

Алгоритм можна розділити на дві основні частини: злиття та вставка.

I — Злиття

Частина злиття досить проста: ми розбиваємо числа на менші пари та зливаємо їх. Розмір пар визначається в порядку зростання до того моменту, поки не можна сформувати більше однієї пари.

1. Розділити список на менші пари.

На цьому етапі ми розбиваємо числа на пари (підсписки). Кожна пара може містити більше одного числа, залежно від порядку, і кожного разу ми множимо порядок на 2 під час повторення алгоритму. Потім ми сортуємо пари.
Наприклад:

Набір цих чисел: 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0

У порядку 1, ми створюємо пари: [25], [24], [23], [22], [21], [20], [19], [18], [17], [16], [15], [14], [13], [12], [11], [10], [9], [8], [7], [6], [5], [4], [3], [2], [1], [0].

2. Сортуємо кожну пару окремо за допомогою сортування вставками.

Ми сортуємо пари на основі останнього числа кожної пари.
Наприклад, у попередньому прикладі ми мали:

[25], [24], [23], [22], [21], [20], [19], [18], [17], [16], [15], [14], [13], [12], [11], [10], [9], [8], [7], [6], [5], [4], [3], [2], [1], [0]

Ми порівнюємо останній елемент кожної пари з наступною парою і міняємо їх місцями в порядку сортування:

— Порівнюємо 25 і 24, міняємо місцями: 24, 25
— Порівнюємо 23 і 22, міняємо місцями: 22, 23
— Порівнюємо 21 і 20, міняємо місцями: 20, 21
— Продовжуємо цей процес для всього списку.

Результат після першого проходу:

24, 25, 22, 23, 20, 21, 18, 19, 16, 17, 14, 15, 12, 13, 10, 11, 8, 9, 6, 7, 4, 5, 2, 3, 0, 1

генерація пар

3. Повторюємо з збільшенням порядку.

Ми повторюємо процес із збільшенням порядку, множачи порядок на 2 щоразу.

злиття

II — Вставка

Тут стає доволі складно.
Пам'ятаємо порядок, який ми використовували для створення пар.

Ми створюємо два набори: один відсортований набір, який називається main, та інший набір, який називається pend. Потім ми сортуємо пари з набору pend у набір main за допомогою бінарного пошуку у зворотному порядку, ділячи порядок на 2 на кожному кроці.

1. Генерація pend та main.

На цьому етапі ми генеруємо два набори пар: один, який називається main, і інший, який називається pend.

Ми розділяємо елементи з кінця останнього злиття на пари на основі їх порядку.
Це призводить до набору на зразок цього: a1 b1 a2 b2 a3 b3 a4 b4 a5 b5 ….

Набір main міститиме a1 b1 разом із рештою елементів b, тоді як набір pend міститиме залишкові елементи a.

Наприклад, для набору чисел {10, 11, 12, 13, 14, 15, 16, 17…} у порядку 2:

a1 = [10, 11]

b1 = [12, 13]

a2 = [14, 15]

b2 = [16, 17]

Набори виглядатимуть ось так:

main: [10, 11], [12, 13], [16, 17] …

pend: [14, 15] …

Якщо ми стикаємось з непарною парою, ми зберігаємо її для наступного кроку. Крім того, елементи, з яких не можна сформувати пару (залишкові елементи), також зберігаються окремо.

2. Сортування

На цьому етапі ми сортуємо пари з pend у набір main на основі останнього елемента кожної пари.
Ми використовуємо бінарний пошук, оптимізований за допомогою послідовності Якобстала, і повторюємо процес, щоразу ділячи порядок (розмір пари) на 2.

Приклад:

Дано набори:

main: [10, 11], [12, 13], [16, 17] …

pend: [14, 15]

Кроки:

Сортування пар з Pend:
Для кожної пари в pend порівнюємо її останній елемент з останніми елементами пар у main. Використовуємо бінарний пошук (з оптимізацією за допомогою послідовності Якобстала), щоб знайти правильну позицію і вставити пару в main.

Обробка непарних пар:
Якщо є непарна пара (пара, яка не підходить для основної послідовності), сортуємо її в main на цьому етапі.

Додавання залишкових елементів:
Будь-які елементи, з яких не можна сформувати пару, додаються до main як окремі елементи.

Повторення процесу:
Після сортування всіх пар і обробки залишкових елементів ділимо порядок (розмір пари) на 2 і повторюємо весь процес.
Продовжуйте, поки порядок не можна буде поділити далі.

insertion

Приклад реалізації:

В останньому прикладі ми мали числа 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0. Перший раз порядок дорівнює 1, тому в кожній парі є лише один елемент:

Створення пар:

[25], [24], [23], [22], [21], [20], [19], [18], [17], [16], [15], [14], [13], [12], [11], [10], [9], [8], [7], [6], [5], [4], [3], [2], [1], [0]

Сортуємо кожну пару за останнім елементом. На цьому етапі порядок дорівнює 1, тому в парах є лише один елемент. Міняємо місцями 25 і 24, 23 і 22, і так далі. Після цього набір виглядатиме так:

24, 25, 22, 23, 20, 21, 18, 19, 16, 17, 14, 15, 12, 13, 10, 11, 8, 9, 6, 7, 4, 5, 2, 3, 0, 1.

Повторюємо процес, множачи порядок на 2, поки не зможемо більше формувати пари та обмінювати їх місцями.
Тепер розмір пари стане 2:

Отже, [24, 25], [22, 23], [20, 21], [18, 19], [16, 17], [14, 15], [12, 13], [10, 11], [8, 9], [6, 7], [4, 5], [2, 3], [0, 1]

Ми сортуємо кожну пару:

[24, 25], [22, 23], [20, 21], [18, 19], [16, 17], [14, 15], [12, 13], [10, 11], [8, 9], [6, 7], [4, 5], [2, 3], [0, 1]

Результат буде таким:

22, 23, 24, 25, 18, 19, 20, 21, 14, 15, 16, 17, 10, 11, 12, 13, 6, 7, 8, 9, 2, 3, 4, 5, 0, 1

Порядок = 4:

Ми збільшуємо порядок до 4, що означає, що кожна пара тепер містить чотири елементи. Потім ми сортуємо кожну пару за допомогою сортування вставками (insertion sort) і зливаємо їх.

Пари: [22, 23, 24, 25], [18, 19, 20, 21], [14, 15, 16, 17], [10, 11, 12, 13], [6, 7, 8, 9], [2, 3, 4, 5], [0, 1]
— Порівнюємо останні елементи кожної пари та, якщо необхідно, міняємо пари місцями.

Результат після сортування пар з порядком = 4:

18, 19, 20, 21, 22, 23, 24, 25, 10, 11, 12, 13, 14, 15, 16, 17, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1

5.
Порядок = 8:

Ми збільшуємо порядок до 8, що означає, що кожна пара тепер містить вісім елементів. Потім ми сортуємо кожну пару за допомогою сортування вставками (insertion sort) і зливаємо їх.

Пари: [18, 19, 20, 21, 22, 23, 24, 25], [10, 11, 12, 13, 14, 15, 16, 17], [2, 3, 4, 5, 6, 7, 8, 9], [0, 1]
— Порівнюємо останні елементи кожної пари та, якщо необхідно, міняємо пари місцями.

Результат після сортування пар з порядком = 8:

10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1

Порядок = 16

Коли порядок досягає 16, він стає меншим за половину розміру списку. Іншими словами, ми більше не можемо створити дві пари для їх обміну. У цей момент ми починаємо використовувати сортування вставками (insertion sort). Ми ділимо порядок на 2 і починаємо сортувати за допомогою сортування вставками.

7.
Порядок вставки = 8

Тут ми генеруємо main та pend, і починаємо сортувати pend в main.

Генеруємо пари:

a1 = [10, 11, 12, 13, 14, 15, 16, 17]

b1 = [18, 19, 20, 21, 22, 23, 24, 25]

a2 = [2, 3, 4, 5, 6, 7, 8, 9]

Залишки: [0, 1]

Тепер сортуємо a2 в main (a1 та b1):

Порівнюємо кожен елемент з a2 з елементами в main, вставляючи кожен елемент з a2 на своє правильне місце.

Після сортування результат виглядає так: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]

Оскільки залишкові елементи [0, 1] менші за всі елементи в main, вони поки залишаються несортованими.

Порядок = 4

Генеруємо пари за розміром = порядок:

a1 = [2, 3, 4, 5]

b1 = [6, 7, 8, 9]

a2 = [10, 11, 12, 13]

b2 = [14, 15, 16, 17]

a3 = [18, 19, 20, 21]

b3 = [22, 23, 24, 25]

Залишки: [0, 1]

Тепер:

Main = a1, b1, a2, b2

Pend = a3, b3

Нечіткі залишки = [0, 1]

Тепер сортуємо елементи з pend (a3, b3) в main.
Після сортування результат виглядає так: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]

Залишкові елементи [0, 1] досі менші за елементи в main.

Порядок = 2

Генеруємо пари за розміром = порядок:

a1 = [2, 3]

b1 = [4, 5]

a2 = [6, 7]

b2 = [8, 9]

a3 = [10, 11]

b3 = [12, 13]

a4 = [14, 15]

b4 = [16, 17]

a5 = [18, 19]

b5 = [20, 21]

a6 = [22, 23]

b6 = [24, 25]

Залишки: [0, 1]

Сортуємо залишки [0, 1] в main. Після сортування список виглядає так: [0, 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]

Порядок = 1

Нарешті, досягаємо порядку = 1. На цьому етапі кожен елемент є окремою парою.
Оскільки список вже відсортований, подальші операції не потрібні.

Остаточний відсортований список

0, 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

Реалізація коду

template   
int PmergeMe::Jacobsthal(int k) {  
 // Обчислює k-те число Якобстала за формулою: J(k) = (2^(k+1) + (-1)^k) / 3.  
 // Числа Якобстала використовуються для визначення індексів для обробки елементів у певному порядку  
 // під час етапу вставки алгоритму сортування. Послідовність Якобстала допомагає оптимізувати бінарний пошук   
 // під час вставки, надаючи ефективний порядок для вставки елементів.
return round((pow(2, k + 1) + pow(-1, k)) / 3);  
}  

template   
void PmergeMe::insert(Container &main, Container &pend, ValueType odd, Container &left, Container &vec, bool is_odd, int order) {  
 // Вставляє елементи з контейнера 'pend' в контейнер 'main' у відсортованому порядку.  
 // Цей метод обробляє процес злиття, описаний у статті, де пари з 'pend' вставляються  
 // у 'main' за допомогою бінарного пошуку, оптимізованого за допомогою послідовності Якобстала.  

 Iterator end;  

 // Якщо в 'pend' є лише один елемент, сортуємо за допомогою звичайного бінарного пошуку.  
 if (pend.size() == 1) {  
 end = std::upper_bound(main.begin(), main.end(), *pend.begin());  
 main.insert(end, *pend.begin());  
 } else if (pend.size() > 1) {  
 // Обробляємо 'pend' за допомогою послідовності Якобстала для визначення індексів вставки.
size_t jc = 3; // Почати з 3-го числа Якобстала  
 size_t count = 0;  
 size_t idx;  
 size_t decrease;  

 // Сортуємо 'pend' у 'main' за допомогою бінарного пошуку 'upper_bound' з оптимізацією через Якобстал.  
 while (!pend.empty()) {  
 idx = Jacobsthal(jc) - Jacobsthal(jc - 1);  
 if (idx > pend.size())  
 idx = pend.size();  

 decrease = 0;  
 while (idx) {  
 // Визначаємо точку вставки на основі індексу Якобстала та вставляємо елемент.  
 end = main.begin();  
 if (Jacobsthal(jc + count) - decrease <= main.size())  
 end = main.begin() + Jacobsthal(jc + count) - decrease;  
 else  
 end = main.end();  
 // Бінарне сортування  
 end = std::upper_bound(main.begin(), end, *(pend.begin() + idx - 1));  
 main.insert(end, *(pend.begin() + idx - 1));  
 pend.erase(pend.begin() + idx - 1);  

 idx--;  
 decrease++;  
 count++;  
 }  
 jc++;  
 }  
 }  

 Container yaslam;  

 // Якщо є непарний елемент, сортуємо його за допомогою звичайного бінарного пошуку.
if (is_odd) {  
 end = std::upper_bound(main.begin(), main.end(), odd);  
 main.insert(end, odd);  
 }  
 // Перебудова 'main' на основі відсортованих останніх елементів.  
 for (Iterator i = main.begin(); i != main.end(); i++) {  
 Iterator it = std::find(vec.begin(), vec.end(), *i);  
 yaslam.insert(yaslam.end(), it - (order - 1), it + 1);  
 }  
 yaslam.insert(yaslam.end(), left.begin(), left.end());  
 vec = yaslam;  
}  

template   
void PmergeMe::sort(Container &vec) {  
 // Рекурсивна функція сортування з використанням пар і вставок.  
 static int order = 1; // Починаємо з одиничного розміру для пар.  

 int unit_size = vec.size() / order; // Поточний розмір одиниці визначається порядком.  
 if (unit_size < 2)  
 return; // Якщо розмір одиниці менший за 2, немає потреби продовжувати сортування.  

 bool is_odd = unit_size % 2 == 1; // Перевірка, чи поточний розмір одиниці непарний.
Iterator start = vec.begin();  
 Iterator end = vec.begin() + ((order * unit_size) - (is_odd * order));  

 // Виконання порівнянь і обміну елементів для поточного порядку.  
 // Цей крок забезпечує правильне сортування елементів у кожній парі.  
 for (Iterator it = start; it < end; it += (order * 2)) {  
 if (*(it + (order - 1)) > *(it + ((order * 2) - 1))) {  
 for (int i = 0; i < order; i++) {  
 std::swap(*(it + i), *(it + i + order));  
 }  
 }  
 }  

 order *= 2; // Подвоюємо порядок для наступної ітерації.  
 sort(vec); // Рекурсивний виклик.  
 order /= 2; // Скидаємо порядок до попереднього значення після рекурсивного виклику.  

 Container main; // Контейнер для останнього елемента з кожної пари.  
 Container pend; // Контейнер для останнього елемента з кожної пари.  
 ValueType odd = 0;  
 Container left;  

 // Генерація контейнерів 'main' і 'pend' на основі поточного порядку.  
 main.push_back(*(start + order - 1)); // Додаємо елемент з кінця першої пари (a1).
main.push_back(*(start + order * 2 - 1)); // Додаємо елемент з кінця другої пари (b1).  

 for (Iterator it = start + order * 2; it < end; it += order) {  
 pend.push_back(*(it + order - 1)); // Додаємо елементи з 'pend' до 'main'.  
 it += order;  
 main.push_back(*(it + order - 1)); // Додаємо елементи з 'main' до 'pend'.  
 }  

 if (is_odd)  
 odd = *(end + order - 1); // Зберігаємо непарну пару, якщо така є  

 left.insert(left.end(), end + (order * is_odd), vec.end()); // Зберігаємо залишкові елементи, які не можуть утворити пари.  

 // Виконуємо вставку.
if (is_odd || !pend.empty())  
 insert(main, pend, odd, left, vec, is_odd, order);  
}

[

GitHub - w0rmr/cpp09

Співпрацюйте у розробці w0rmr/cpp09, створивши обліковий запис на GitHub.

github.com

](https://github.com/w0rmr/cpp09?source=post_page-----e6ad43288d4b--------------------------------)

Не соромтеся надавати відгуки, виправлення або пропозиції для покращення

корисні ресурси:

[

Алгоритм бінарного пошуку - ітеративна та рекурсивна реалізація - GeeksforGeeks

Портал комп'ютерних наук для гіків. Вміщує добре написані, продумані та пояснені матеріали з комп'ютерних наук.

www.geeksforgeeks.org

](https://www.geeksforgeeks.org/binary-search/?source=post_page-----e6ad43288d4b--------------------------------)

[

Людське пояснення та покрокова візуалізація алгоритму Форда-Джонсона

Алгоритм сортування Форда-Джонсона, або сортування злиттям та вставкою, не є дуже відомим, але він є...

Tagged with…

dev.to

](https://dev.to/emuminov/human-explanation-and-step-by-step-visualisation-of-the-ford-johnson-algorithm-5g91?source=post_page-----e6ad43288d4b--------------------------------)

[

Merge Sort - Підручники з алгоритмів і структур даних - GeeksforGeeks

Як і QuickSort, Merge Sort є алгоритмом поділу та завоювання. Він ділить вхідний масив на дві частини, викликає себе для...