Методы сортировки

МИНОБРНАУКИ РОССИИ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ

ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

«ЛЭТИ» ИМ. В.И. УЛЬЯНОВА (ЛЕНИНА)

Кафедра ИБ

ОТЧЕТ

по лабораторной работе № 1

по дисциплине «Алгоритмы и структуры данных»

Тема: Методы сортировки

Санкт-Петербург

2020

1. Цель работы

Ознакомление с алгоритмами сортировки линейных и нелинейных структур и методикой оценки эффективности алгоритмов.
Вариант 17, реализуемый в работе метод сортировки: метод Шелла.

2. Формулировка задания

Реализовать алгоритм сортировки в соответствии со своим вариантом, предусмотреть в программе учёт времени сортировки структур. Программа должна иметь графический интерфейс. Произвести расчёт функции сложности разработанного алгоритма по полученным временным затратам.

3. Теоретическая часть

Различные методы сортировки можно увидеть на рисунке 1.

[pic 1]

Рисунок 1 - Методы сортировки

Метод Шелла относится к сортировке обменом в линейных структурах. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии  друг от друга.  где  – количество сортируемых данных. После каждого просмотра шаг d уменьшается вдвое. На последнем просмотре шаг  уменьшается до 1.[pic 2][pic 3][pic 4][pic 5]

Пример: имеется массив из 8 элементов
, . Сначала группируются и сортируются элементы, отстоящие друг от друга на расстоянии 4
(см рисунок 2). После сортируются элементы, отстоящие друг от друга на расстоянии 2 (см рисунок 3) и, наконец, на расстоянии 1 (см рисунок 4). После первой сортировки , после второй - 
. Последняя одинарная сортировка в результате даёт нам отсортированный массив .[pic 6][pic 7][pic 8][pic 9][pic 10]

[pic 11]

Рисунок 2 - Сортировка элементов на расстоянии 4

[pic 12]

Рисунок 3 - Сортировка элементов на расстоянии 2

[pic 13]

Рисунок 4 - Сортировка элементов на расстоянии 1

Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки, например, пузырьковой, каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, а при сортировке Шелла это число может быть больше).

Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:

• отсутствие потребности в памяти под стек;
• отсутствие деградации при неудачных наборах данных — быстрая сортировка легко деградирует до , что хуже, чем худшее гарантированное время для сортировки Шелла.[pic 14]

4. Блок-схема

Блок-схема функции, реализующей метод сортировки приведена в приложении 1.

5. Демонстрация работы программы

Вид графического интерфейса представлен на рисунке 5.

[pic 15]

Рисунок 5 - Вид графического интерфейса программы

Программа обрабатывает некорректный ввод количества элементов
массива (рисунок 6).

[pic 16]

Рисунок 6 - Обработка некорректного ввода длины массива

Программа обрабатывает некорректный ввод границ значений элементов массива (рисунок 7).

[pic 17]

Рисунок 7 - Обработка некорректного ввода границ значений элементов массива