Материал: GrozI_Course_Work

1

Зміст

РОЗДІЛ 1 ВСТУПНА ЧАСТИНА 1. Вступ

РОЗДІЛ 2 ОПИС, АНАЛІЗ, РЕАЛІЗАЦІЯ АЛГОРИТМІВ СОРТУВАННЯ

2. Список алгоритмів сортування

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

2.1.1.Аналіз сортування вибором

2.1.2Реалізація

2.2.Сотування вставкою

2.2.1Аналіз сотування вставкою

2.2.2Реалізація

2.3.Шейкерне сортування

2.3.1Аналіз шейкерного сортування

2.3.2Реалізація

2.4.Сортування підрахунком

2.4.1Аналіз сортування підрахунком

2.4.2Реалізація

2.5.Швидке сортування

2.5.1.Аналіз швидкого сортування

2.5.2Реалізація

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

2.6.1Аналіз сортування злиттям

2.6.2Реалізація

2.7.Пірамідальне сортування

2.7.1.Аналіз пірамідального сортування

2.7.2 Реалізація РОЗДІЛ 3 МЕТОДОЛОГІЯ ТЕСТУВАННЯ

1.Апаратне забезпечення

2.Програмне забезпечення

3.Тестові дані

РОЗДІЛ 4 ПОРІВНЯННЯ РОБОТИ АЛГОРИТМІВ СОРТУВАННЯ 1. Тестування

1.1.Довільні дані ,I-група

1.2.Довільні дані ,1I-група

2.1.Реверсивно відсортовані дані,I-група

2.2.Реверсивно відсортовані дані,II-група

3.1.Частково відсортовані дані,I-група

3.2.Частково відсортовані дані,II-група

4.1.Відсортовані дані,I-група

4.2.Відсортовані дані,II-група

2

Вступ

Проблема сортування - одна з найбільш давніх проблем інформатики. З самого початку епохи комп’ютерних обчислень багато дослідників виводили та аналізували проблеми алгоритмім сортування. Розвиток та дослідження проблеми сортування даних проходили поетапно на протязі багатьох років. На даний момент перший єтап ручного сортування, який проходив ще до винайдення перших ЕОМ, нас не цікавить. Тому перейдемо одразу до другого етапу розвитку способів та алгоритмів сортування , який бере свій початок у 1940 році з появи перших електронно обчислювальних машин. У 1946 році вийшла перша стаття про алгоритми сортування даних, автором якої був Джон Вільям Мочлі (John William Mauchly) - американський фізик і інженер, один з творців першого в світі електронного цифрового комп'ютера загального призначення ENIAC. У статті розглядався цілий ряд нових алгоритмів сортування, в тому числі метод бінарних вставок.

До середини 1950-х років найбільш поширеними були модифікації сортування злиттям і вставками складності O (n log n) для n елементів. У середині 1950-х років з появою перших високорівневих мов програмування почався вибуховий розвиток алгоритмів сортування. У 1959 році Дональд Левіс Шелл (Donald Lewis Shell) запропонував метод сортування з спадним кроком (shellsort), в 1960 році Чарльз Ентоні Річард Хоар (Charles Antony Richard Hoare) - метод швидкого сортування (quicksort), в 1964 році Дж. У . Дж. Вільямс (JVJ Williams) - метод пірамідального сортування (heapsort). Багато з розроблених в цей період алгоритмів широко використовуються в наш час. Підсумки цього етапу активного розвитку алгоритмів сортування підвів в 1973 році Дональд Кнут (Donald Ervin Knuth) у третьому томі своєї фундаментальної монографії «Мистецтво программування» ( «The Art of Computer Programming»).

До початку 1970-х років використовувалися наступні види алгоритмів внутрішнього сортування: сортування по засобом підрахунку; сортування шляхом вставок; обмінна сортування; сортування за допомогою вибору; сортування методом злиття; сортування методом розподілу. Найбільша кількість розроблених на той час методів відносилося до сортування шляхом вставок (метод простих вставок, бінарні і двоколійних вставки, метод Шелла, вставка в списокта ін.), Обмінного сортування (метод бульбашки і його модифікації, паралельне сортування Бетчера, швидке сортування, обмінне сортування за розрядами, асимптотичні методи) і сортування за допомогою вибору (вибір з дерева, пірамідальна сортування, метод виключення найбільшого з включених, метод пов'язанийного уявлення пріоритетних черг). Не менш активно розроблялися і методи зовнішньої сортування, в тому числі методи багатоколійного злиття і вибору з заміщенням, багатофазного злиття, каскадного злиття, зовнішнього порозрядного сортування і т. д.

4

Список алгоритмів сортування

Для порівняння та реалізації мною вибрані такі алгоритми сортування:

1.Сортування вибором (Selection sort)

2.Сотування вставкою (Insertion sort)

3.Шейкерне сортування (Shaker sort)

4.Сортування підрахунком (Counting sort)

5.Швидке сортування (Quick sort)

6.Сортування злиттям (Merge sort)

7.Пірамідальне сортування (Heap sort)