я якого виконано на суміжній пам'яті. Для більшої ефективності пошуку елементів треба, щоб шляху доступу до них стали коротшими, ніж просто послідовний перебір. Найбільш очевидний метод: почати пошук з середнього елемента, тобто виконати порівняння з елементом а. Результат порівняння дозволить визначити, в якій половині послідовності а {, а 2 , ..., а, 1 + ",, ..., а п продовжити пошук,
застосовуючи до ній ту ж процедуру, і т.д. Основна ідея бінарного пошуку досить проста, проте В«для багатьох хороших програмістів не одна спроба написати правильну програму закінчилася невдачею В». Щоб досконально розібратися в алгоритмі, найкраще представити дані а х <а 2 < ... < а п у вигляді двійкового дерева порівнянь, яке відповідає бінарним пошуку. p> Двійкове дерево називається деревом порівнянь , якщо для будь-якої його вершини (кореня дерева або кореня поддерева) виконується умова:
{Вершини лівого піддерева} <Вершина кореня <{Вершини правого поддерева }.
В
Рис . Приклад дерева порівнянь, що відповідає бінарним пошуку серед сортованих елементів: 3,5,7,9,12,19,27,44
Т.ч. бінарний пошук - це порівняння еталону х, яке здійснюється з елементом, розташованим в середині масиву і залежно від результату порівняння (Більше або менше) подальший пошук проводиться в лівій або правій половині масиву. p> Використовується, коли є яка-небудь інформація про масиві, наприклад масив впорядкований по неспадання. Загальне кількість порівнянь має порядок О (N * logN).
В В В
Методи сортування.
Сортування злиттями.
Використовується, коли необхідно об'єднати впорядковані фрагменти масивів: A [k], ..., A [m] і B [m +1], ..., B [q] в один C [k], ..., C [q], теж впорядкований (k <= m <= q). Основна ідея рішення полягає в порівнянні чергових елементів кожного фрагмента, з'ясуванні, який з елементів менше, перенесення його в допоміжний масив С (для простоти) та просуванні по того фрагменту масиву, з якого взято елемент. При цьому варто не забути записати в С решту того фрагмента, який не встиг себе В«ВичерпатиВ». p> Метод злиттів - один з перших в теорії алгоритмів сортування. Він запропонований Дж. Фон Нейманом в 1945 році. Ефективність алгоритму, за Д. Кнуту, становить С = О (N * logN). <В
Швидке сортування Хоара.
Метод запропонований Ч.Е.Р.Хоаром в 1962 році. p> Ідея методу. У вихідному масиві А вибирається певний елемент Х (бар'єрний елемент). Основною метою алгоритму є запис Х В«на своє місцеВ» в масиві, нехай це буде місце k, таке, що зліва від Х були елементи масиву, менші або рівні Х, а праворуч - елементи масиву, великі Х, тобто масив А буде мати вид: (А [1], A [2], ..., A [k-1]), A [k] (X), (A [k +1], ..., A [n]). p> У результаті елемент A [k] знаходитьс...
