• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Метод простого включення

Сортування злиттям

Сортування за допомогою дерева

Сортування вибором

Метод Шелла

Метод простого включення

План

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 порівнянь і стільки ж пересилань. Отже, можна оцінювати складність методу простих включень як Θ (n²).

Можна скоротити кількість порівнянь, що використовуються в методі простих включень, якщо скористатися тим фактом, що при опрацюванні елемента масиву а[і] елементи а[1], а[2], ..., a[i-1] вже впорядковані, і скористатися для пошуку елементу, з яким має виконуватись перестановка, методом двійкового розподілу. У цьому випадку оцінка кількості необхідних порівнянь стає Θ (nlog n). Зазначимо, що оскільки при виконанні перестановки потрібне зсування на один елемент декількох елементів, то оцінка кількості пересилань залишається Θ (n²). .

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];

}

Читайте також:

1. D) методу мозкового штурму.
2. H) інноваційний менеджмент – це сукупність організаційно-економічних методів управління всіма стадіями інноваційного процесу.
3. I Метод Шеннона-Фано
4. I. Метод рiвних вiдрiзкiв.
5. VII. Нахождение общего решения методом характеристик
6. А. науковий факт, b. гіпотеза, с. метод
7. Автоматизація водорозподілу на відкритих зрошувальних системах. Методи керування водорозподілом. Вимірювання рівня води. Вимірювання витрати.
8. Агрегативна стійкість, коагуляція суспензій. Методи отримання.
9. АгротехнІЧНИЙ метод
10. Адаптовані й специфічні методи дослідження у журналістикознавстві
11. Адміністративні (прямі) методи регулювання.
12. Адміністративні методи - це сукупність прийомів, впливів, заснованих на використанні об'єктивних організаційних відносин між людьми та загальноорганізаційних принципів управління.

Переглядів: 1940