Программная реализация алгоритмов сортировки массивов: сортировка расчёской, поразрядная сортировка(LSD) и их сравнение по быстродействию

[pic 1]

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ

УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ

(НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ)» (МАИ)

Кафедра 318 «Информационные и сетевые технологии»

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

К курсовой работе

по дисциплине: “Алгоритмические языки программирования”

Тема

“Программная реализация алгоритмов сортировки массивов: сортировка расчёской, поразрядная сортировка(LSD) и их сравнение по быстродействию”

Листов  9

Работу проверил                                                 Задание принял к исполнению _______ / Жарков С. В.                                  студент группы М3О-135Б-18

«__»___________2018 г.                                ______/ Кузнецов А. А.                 

                                                                  «__»___________2018 г.

г. Москва

2018

Оглавление

1.Постановка задачи3

2.Алгоритмы сортировки3

3. Обзор алгоритмов сортировки 4

3.1. Сортировка расческой (Comb Sort) 4

3.2. Поразрядная сортировка (Radix Sort(LSD)) 5

4. Программная реализация алгоритмов6

5. Подробное описание алгоритмов7

6. Сравнение алгоритмов сортировки8

7. Используемые материалы9

8. Приложение №19

1. Постановка задачи

Дано: одномерный массив, состоящий из n чисел (символов).

Цель: отсортировать этот массив по возрастанию с помощью сортировки расческой и поразрядной сортировки и сравнить их по быстродействию.

Результат: отсортированный массив и время выполнения функции сортировки.

Краткие характеристики ПК и программного обеспечения, использованных для выполнения и оформления пояснительного листа:

• AMD A9 9425 Частота: 3.1 ГГЦ;
• Оперативная память 8192 Мб, DDR4, 2133 МГц;
• Видеокарта AMD RADEON R5;
• Microsoft Windows 10;
• Microsoft Visual Studio 2017.

2. Алгоритмы сортировки

Алгоритм сортировки — это алгоритм для упорядочения элементов в списке.

Оценка алгоритма сортировки

Для того, чтобы обоснованно сделать такой выбор, рассмотрим параметры, по которым будет производиться оценка алгоритмов.

• Время сортировки — основной параметр, характеризующий быстродействие алгоритма.
• Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. При оценке используемой памяти не будет учитываться место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы.

3.Обзор алгоритмов сортировки

Сортировка расческой

Сортировка расчёской (англ. comb sort) — это довольно упрощённый алгоритм сортировки. Основная идея — устранить черепах, или маленькие значения в конце списка, которые крайне замедляют сортировку пузырьком.

Алгоритм.

Основная идея «расчёски» в том, чтобы первоначально брать достаточно большое расстояние между сравниваемыми элементами и по мере упорядочивания массива сужать это расстояние вплоть до минимального. Таким образом, мы как бы причёсываем массив, постепенно разглаживая на всё более аккуратные пряди. Первоначальный разрыв между сравниваемыми элементами лучше брать с учётом специальной величины, называемой фактором уменьшения, оптимальное значение которой равно примерно 1,3 (const float gap_number = 1.3). Сначала расстояние между элементами равно размеру массива(int n), (int gap = n), разделённого на фактор уменьшения (результат округляется до ближайшего целого) (gap /= gap_number). Затем, пройдя массив с этим шагом, необходимо поделить шаг на фактор уменьшения и пройти по списку вновь(через цикл while (gap >= 1)). Так продолжается до тех пор, пока разность индексов не достигнет единицы(). В этом случае массив досортировывается обычным пузырьком.