ерестановок також бути не може. Тобто ці частини можна сортувати незалежно один від одного. p>. Якщо В«меншаВ» або В«великаВ» частина складається з одного елемента, то вона вже відсортована і робити нічого не треба. Інакше сортуємо ці частини за допомогою алгоритму швидкого сортування (тобто, виконуємо для неї кроки 1-3). p> Як бачите, швидке сортування складається з виконання кроків 1 і 2 та рекурсивного виклику алгоритму для одержані частин масиву.
Алгоритм 2: Сортування злиттям (merge sort).
Ділимо масив на дві частини приблизно однакового розміру і, якщо вийде половина масиву містить більше одного елемента, то сортуємо її за допомогою сортування злиттям. Як бачите, цей пункт містить рекурсивне звернення до всього алгоритму в цілому. p> З'єднуємо дві відсортовані половини так, щоб вийшов один відсортований масив. Для цього поміщаємо в допоміжний масив елементи з першої половини, поки вони не перевершують чергового елемента з другої половини. Потім починаємо поміщати туди елементи другої половини, поки вони не перевершують чергового елемента з першої половини. Потім знову беремо елементи першої половини і т.д. Ця операція називається злиттям і вимагає стільки кроків, скільки елементів в обох з'єднуються масивах. p> Алгоритм 3: Сортування деревом (tree sort).
Перш ніж переходити до пояснення суті алгоритму введемо одне поняття. Двійковим деревом пошуку називається бінарне дерево, у вузлах якого розташовуються числа таким чином, що в лівому поддереве кожного вузла знаходяться числа менші, ніж в цьому вузлі, а в правому поддереве більше або рівні того, що в цьому вузлі. На рис. 10 показано два приклади дерев пошуку, складених з одних і тих же чисел. br/>В
Рис. 10. Двійкові дерева пошуку, складені з чисел 1, 3, 4, 6, 7, 8, 10, 13, 14. br/>
Якщо для кожної вершини висота піддерев відрізняється не більше ніж на одиницю, то дерево називається збалансованим. Збалансовані дерева пошуку також називаються АВЛ-деревами (за першими літерами прізвищ винахідників Г. М. Адельсона-Бєльського і Е. М. Ландіса). Як видно на рис. 10а показано збалансоване дерево, на рис. 10б незбалансоване. p> Зауважимо, що розташування чисел у зростанню вийде, якщо обходити ці дерева в зворотному прядки.
Сортування деревом вийде, якщо ми спочатку послідовно будемо додавати числа з масиву в двійкове дерево пошуку, а потім обійдемо його в зворотному порядку.
Якщо дерево буде близько до збалансованого, то сортування потребують приблизно n log2 n операцій. Якщо не пощастить і дерево виявиться максимально незбалансованим, то сортування забере n2 операцій. br/>
.5 Довільна кількість вкладених циклів
Розмістивши рекурсивні виклики всередині циклу, по суті, отримаємо вкладені цикли, де рівень вкладеності дорівнює глибині рекурсії.
Для прикладу напишемо процедуру, друкувальну всі можливі поєднання з k чисел від 1 до n (). Числа, що входять в кожне поєднання, будемо друкувати в поря...
