МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів Контакти
Тлумачний словник |
|
||||||||||||||||||||||||||||||||||
Метод простого включенняСортування злиттям Сортування за допомогою дерева Сортування вибором Метод Шелла Метод простого включення План
2 Сортування шляхом підрахунку 4 Обмінне сортування 6 Сортування поділом (Хоара) 8 Пірамідальне сортування 9 Побудова піраміди методом Флойда
У загальній постановці завдання сортування ставиться таким чином. Є послідовність однотипних записів, одне з полів яких вибране як ключове (далі ми називатимемо його ключем сортування). Тип даних ключа повинен включати операції порівняння («=», «>», «<», «>=» і «<=»). Завданням сортування є перетворення початкової послідовності в послідовність, що містить ті самі записи, але у порядку зростання (або спадання) значень ключа. Метод сортування називається стійким, якщо при його застосуванні не змінюється відносне положення записів із рівними значеннями ключа. Розрізняють сортування масивів записів, розташованих в основній пам'яті (внутрішнє сортування), і сортування файлів, що зберігаються в зовнішній пам'яті і не вміщуються повністю в основній пам'яті (зовнішнє сортування). Для внутрішнього і зовнішнього сортування потрібні істотно різні методи. Природною умовою, що висувається до будь-якого методу внутрішнього сортування є те, що ці методи не повинні вимагати додаткової пам'яті: всі перестановки з метою впорядкування елементів масиву мають вироблятися в межах того ж масиву. Мірою ефективності алгоритму внутрішнього сортування є кількість необхідних порівнянь значень ключа (С) і кількість перестановок елементів (М). Зазначимо, що оскільки сортування засноване тільки на значеннях ключа і ніяк не зачіпає поля записів, що залишилися, можна говорити про сортування масивів ключів.
Нехай є масив ключів а[1], а[2], ..., а[n]. Для кожного елемента масиву, починаючи з другого, здійснюється порівняння з елементами з меншим індексом (елемент а[і] послідовно порівнюється з елементами а[і-1], а[і-2]...) і до тих пір, поки для чергового елемента a[j] виконується співвідношення а[j]> а[і], а[і] і a[j] міняються місцями. Якщо вдається зустріти такий елемент a[j], що a[j]<= a[i], або якщо досягнута нижня межа масиву, здійснюється перехід до опрацювання елемента a[i+1] (поки не буде досягнута верхня межа масиву) (рисунок 14).
Рисунок 14 – Блок-схема сортування методом включення
Можна побачити, що в кращому разі (коли масив вже впорядкований) для виконання алгоритму з масивом із n елементів буде треба n-1 порівняння і 0 пересилань. У гіршому разі (коли масив впорядкований у зворотному порядку) буде треба n*(n-1)/2 порівнянь і стільки ж пересилань. Отже, можна оцінювати складність методу простих включень як Θ (n2). Можна скоротити кількість порівнянь, що використовуються в методі простих включень, якщо скористатися тим фактом, що при опрацюванні елемента масиву а[і] елементи а[1], а[2], ..., a[i-1] вже впорядковані, і скористатися для пошуку елементу, з яким має виконуватись перестановка, методом двійкового розподілу. У цьому випадку оцінка кількості необхідних порівнянь стає Θ (nlog n). Зазначимо, що оскільки при виконанні перестановки потрібне зсування на один елемент декількох елементів, то оцінка кількості пересилань залишається Θ (n2). .
Void sort_vstavka() { Int I,j; int a[50], a1; Int k[50]; i=0; while(i<50) { for (j=i-1; j>=0; j—) { if (a[j]>a[i]) { a1=a[j]; a[j]=a[i]; a[i]=a1; i--; } } i++; } }
Таблиця 1 – Приклад сортування методом простого включення.
2 Сортування шляхом підрахунку
Кожний елемент порівнюється зі всіма іншими; остаточно положення елементів визначаються після підрахунку кількості менших ключів. Треба знайти перестановку р(1) р(2)...р(n), таку, що Кр(1)<=Кр(2)<=...<=Кр(n). Метод заснований на тому що j-ключ впорядкованої послідовності перевищує рівно j-1 інших ключів. Ідея полягає в тому, щоб зрівняти попарно всі ключі і підрахувати, скільки з них менші від кожного окремого ключа. Спосіб виконання поставленого завдання такий: ((порівняти Кj із Кі) при l<=j<i) при 1<i<=N.
Void sort_pidr() { int i,j; int a[50], a1[50]; int k[50]; for (i=0; i<50; i++) k[i]=0; for(i=0;i<50-1; i++) for (j=i+1;j<50;j++) if(a[i]<a[j]) k[i]++; else k[j]++; for (i=0; i<50; i++) a1[k[i]]=a[i]; for (i=0; i<50; i++) a[i]=a1[i]; }
Читайте також:
|
|||||||||||||||||||||||||||||||||||
|