Сортування методом "природного злиття”
Умова: задано сукупність (рядок, масив) чисел. Потрібно їх посортувати.
Алгоритм сортування методом "природного злиття” грунтується на таких аспектах:
- Задано масив чисел, які необхідно посортувати;
- Розбуваємо цей масив на два підмасиви за певним правилом; Перше число позамовчуванні записуємо в перший підмасив. Далі, якщо число більше записулємо його також в перший підмасив, якщо менше, то в другий підмасив. Якщо число було записане в другий підмасив, то наступне число (якщо більше) записуємо в цей самий підмасив (якщо менше, то в перший підмасив). Далі все робимо за таким же самим принципом;
- Якщо після розбиття в другому підмасиві нема жодного числа, то ми отримали відсортований масив в першому підмасиві. Йдемо на пункт 5;
- Складаємо з двох масивів за певним правилом числа в один масив. Порівнюємо перші числа з двох підмасивів. Менше записуємо в новий масив та тепер порівнюємо більше з перших і наступне з того масиву, де було перше число менше. І т.д. аж до вичерпання чисел в одному з підмасивів. Решту чисел просто дописуємо в масив. Вертаємося на пункт 2;
- Отримаємо відсортований масив.
|