Дослідження алгоритму сортування

Міністерство освіти та науки України

Вінницький національний технічний університет

Кафедра комп’ютерних наук

Лабораторна робота №4

З дисципліни: “Теорія алгоритмів”

Тема: “Дослідження алгоритму сортування ”

Виконав студент групи 1КН-19б:

Попіль Р.В.

Перевірив викладач:

Арсенюк І.Р.

Вінниця – 2019

Тема: Дослідження та аналіз алгоритмів сортування за лінійний час.

Мета: Ознайомитись з алгоритмами сортування за лінійний час, на прикладі алгоритму сортування вичерпуванням. Вивчити його структуру, зрозуміти принцип дії та поглибити свої знання з теми різних типів сортування.

Ідея алгоритму

Алгоритм сортування вичерпуванням (bucket sort) працює за лінійний середній час. Як і сортування підраховуванням, сортування вичерпуванням застосовується не для будь-яких вихідних даних: вказуючи на лінійний середній час, ми припускаємо, що на вхід подається послідовність незалежних випадкових чисел, рівномірно розподілених на проміжку [0,1]. Ідея алгоритму полягає в тому, що проміжок [0,1] поділяється на n рівних частин, після чого для чисел з кожної частини виділяється свій ящик-черпак (bucket), і n чисел, що підлягають сортуванню, розкладаються по цих ящиках. Оскільки числа рівномірно розподілені на проміжку [0,1], варто очікувати, що в кожному ящику їх буде небагато.

Принцип роботи

Тепер відсортуємо числа в кожному ящику окремо й пройдемося по ящиках у порядку зростання, виписуючи числа, що потрапили в кожний з них, також у порядку зростання. Будемо вважати, що на вхід подається n-елементний масив А, причому 0 ≤ А[i]<1 для всіх i. Використовується також допоміжний масив В[0.. n-1], що складається зі списків, що відповідають ящикам. Алгоритм використовує операції зі списками.

 Псевдокод даного алгоритму матиме вигляд:[pic 1]

Щоб довести, що алгоритм сортування вичерпуванням правильний, розглянемо два числа А[i] та A[j]. Якщо вони потрапили в різні ящики, то менше з них потрапило в ящик з меншим номером, і у вихідній послідовності воно виявиться раніше; якщо вони потрапили в один ящик, то після сортування вмісту ящика менше число буде також передувати більшому.

Аналіз складності алгоритму

Проаналізуємо час роботи алгоритму. Операції у всіх рядках, крім п'ятого, потребують загального часу O(n). Перегляд всіх ящиків також забирає час O(n). Таким чином, нам залишається тільки оцінити час сортування вставками всередині ящиків.  Нехай у ящик В[i] потрапило ni чисел (ni – випадкова величина). Оскільки сортування вставками працює за квадратичний час, математичне очікування часу сортування чисел у ящику номер i має значення O(М[ni2]), а математичне очікування сумарного часу сортування у всіх ящиках має значення

[pic 2]

Знайдемо функцію розподілу випадкових величин ni. Оскільки числа розподілені рівномірно, а довжини всіх відрізків рівні, ймовірність того, що дане число потрапить у ящик номер і, дорівнює 1/n. Отже, ми перебуваємо в відомій ситуації з кулями й урнами: у нас n куль-чисел, n урн-ящиків, і ймовірність влучення даної кулі в дану урну дорівнює  

[pic 3]

Підставляючи цю оцінку в (3.11), одержуємо, що математичне очікування сумарного часу сортування вмісту всіх ящиків має значення O(n), так що математичне очікування часу роботи алгоритму сортування вичерпуванням справді лінійно залежить від кількості чисел. У найгіршому випадку швидкодія буде О(n^2)

Приклад роботи алгоритму:[pic 4]

На рис. 3.23 показано роботу цього алгоритму на прикладі масиву з 10 чисел.  

#include

#include

#include

#include

#include

#include

using namespace std;

static void BucketSort(int* data, int count) {

        int minValue = data[0];

        int maxValue = data[0];

        for (int i = 1; i < count; i++)

        {

                if (data[i] > maxValue)

                        maxValue = data[i];

                if (data[i] < minValue)

...