Файл: Алгоритмы сортировки данных (Понятие алгоритма сортировки).pdf

Сортировка методом выбора (англ. selection sort) — алгоритм сортировки, относящийся к неустойчивым алгоритмам сортировки. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n²), предполагая, что сравнения делаются за постоянное время.

Шаги алгоритма:

1. находим минимальное значение в текущем списке
2. производим обмен этого значения со значением на первой позиции
3. теперь сортируем хвост списка, исключив из рассмотрения уже отсортированный первый элемент.

Пирамидальная сортировка сильно улучшает базовый алгоритм, используя структуру данных ключа для ускорения нахождения и удаления минимального элемента.

Существует также двунаправленный вариант сортировки методом вставок, в котором на каждом проходе отыскивается и устанавливается на своё место и минимальное, и максимальное значения.

Сортировка методом Шелла. Идея алгоритма состоит в обмене элементов, расположенных не только рядом, как в сортировке методом вставок, но и далеко друг от друга, что значительно сокращает общее число операций перемещения элементов.

Для примера возьмем файл из 16 элементов. Сначала просматриваются пары с шагом 8. Это пары элементов 1-9, 2-10, 3-11, 4-12, 5-13, 6-14, 7-15, 8-16. Если значения элементов в паре не упорядочены по возрастанию, то элементы меняются местами. Назовем этот этап 8-сортировкой. Следующий этап — 4-сортировка, на котором элементы в файле делятся на четверки: 1-5-9-13, 2-6-10-14, 3-7-11-15, 4-8-12-16. Выполняется сортировка в каждой четверке.

Следующий этап — 2-сортировка, когда элементы в файле делятся на 2 группы по 8: 1-3-5-7-9-11-13-15 и 2-4-6-8-10-12-14-16. Выполняется сортировка в каждой восьмерке. Наконец весь файл упорядочивается методом вставок. Поскольку дальние элементы уже переместились на свое место или находятся вблизи от него, этот этап будет значительно менее трудоемким, чем при сортировке вставками без предварительных «дальних» обменов.

Анализ алгоритма сортировки Шелла. Время выполнения сортировки пропорционально n^1.2. Эта зависимость значительно лучше квадратичной зависимости n², которой подчиняется большинство простых алгоритмов сортировки.

Пример реализации

Pascal

procedure sort_shell (var a:array of word);

var

bis,i,j,k:longint;

h:word;

begin

bis:=high(a);

k:=bis shr 1;

While k>0 do

Begin

For i:=0 To bis-k do

begin

j:=i;

While (j>=0) And (a[j]>a[j+k]) do

begin

h:=a[j];

a[j]:=a[j+k];

a[j+k]:=h;

dec(j,k);

end;

end;

k:=k shr 1;

End;

End;

Пирамидальная сортировка — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (т.е. гарантированно) за О(n log n) операций при сортировке n элементов.

---

Алгоритм:

Сортировка пирамидой использует сортирующее дерево. Сортирующее дерево – это такое двоичное дерево, у которого выполнены условия:

1. Каждый лист имеет глубину либо d либо d-1
2. Значение в любой вершине больше, чем значения ее потомков.

Удобная структура данных для сортирующего дерева – такой массив Array, что Array[1] – элемент в корне, а потомки элемента Array[i] - Array[2i] и Array[2i+1].

Алгоритм сортировки будет состоять из двух основных шагов:

1. Выстраиваем элементы массива в виде сортирующего дерева:

при

Этот шаг требует О(n) операций.

2. Будем удалять элементы из корня по одному за раз и перестраивать дерево. Т.е. на первом шаге обмениваем Array[1] и Array[n], преобразовываем Array[1], Array[2], ... , Array[n-1] в сортирующее дерево. Затем переставляем Array[1] и Array[n-1], преобразовываем Array[1], Array[2], ... , Array[n-2] в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда Array[1], Array[2], ... , Array[n] - упорядоченная последовательность.

Этот шаг требует О(n log n) операций.

Быстрая сортировка (англ. quicksort) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром. Даёт в среднем O(n log n) сравнений при сортировке n элементов. В худшем случае, однако, получается O(n²) сравнений. Обычно на практике быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(n log n), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре, и на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время.

Интересно, что Хоар разработал этот метод применительно к машинному переводу: дело в том, что в то время словарь хранился на магнитной ленте, и если отсортировать все слова в тексте, их переводы можно получить за один прогон ленты.

Алгоритм. Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:

1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом.
2. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него.
3. Рекурсивно сортируем подсписки, лежащие слева и справа от опорного элемента.

---

Базой рекурсии являются списки, состоящие из одного или двух элементов, которые уже отсортированы. Алгоритм всегда завершается, поскольку за каждую итерацию он ставит по крайней мере один элемент на его окончательное место.

При выборе опорного элемента из данного диапазона случайным образом, худший случай становится очень маловероятным и ожидаемое время выполнения алгоритма сортировки - O(n log n).

ПРАКТИЧЕСКАЯ ЧАСТЬ

2. Практическое задание

Фирма ООО «Стройдизайн» осуществляет деятельность, связанную с выполнением работ по ремонту помещений. Прайс-лист на выполняемые работы приведен на таблице 1. Данные о заказанных работах указаны на таблице 2.

Таблица 1. Прайс-лист на выполняемые работы

Наименование работы	Единица измерения	Цена за ед. изм., руб.
Замена батарей	шт.	250
Замены ванны	шт.	210
Замена труб	м	240
Наклейка обоев	м2	50
Настилка паркета	м2	75
Побелка потолка	м2	15

Таблица 2. Данные о поступившем заказе

Наименование работы	Единица измерения	Объем выполняемых работ	Цена за ед. изм., руб.	Стоимость работ, руб.
Замена батарей	шт.	4
Наклейка обоев	м2	20
Замена труб	м	4
Настилка паркета	м2	15

1. Построить таблицы по приведенным в приложениях данным.
2. Выполнить расчет стоимости выполняемых работ по полученному заказу, данные расчета занести в таблицу (таблица 2).
3. Организовать межтабличные связи для автоматического формирования счета, выставляемого клиенту для оплаты выполняемых работ.
4. Сформировать и заполнить счет на оплату (таблица 3).
5. Результаты расчета стоимости каждого вида работ по полученному заказу представить в графическом виде.

---

Таблица 3. Форма счета на оплату выполненных работ

ООО «Стройдизайн» СЧЕТ № 1 Дата __-__-20__ ФИО клиента _________________ № п/п Наименование работы Единица измерения Объем выполняемых работ Цена за ед. изм., руб. Стоимость работ, руб. 1 Замена батарей шт. 2 Наклейка обоев м2 3 Замена труб м 4 Настилка паркета м2 ИТОГО: НДС: СУММА С НДС: Гл. бухгалтер ______________________________

• 1. Описание алгоритма решения практического задания

Для решения данной экономической задачи была выбрана среда табличного процессора MS Excel. Microsoft Office Excel является средством для создания электронных таблиц, которые обладают возможностями для проведения простых расчетов, как с использованием арифметических действий, так и с помощью встроенных функций; для построения разных типов диаграмм; для оформления полученных таблиц и т.д. Так же, MS Excel – программа, не требующая знаний программирования, достаточно проста в использовании для поиска результата данной задачи.

Порядок выполнения практического задания, следующий:

1. Запустить табличный процессор MS Excel.
2. Создать книгу с именем «Стройдизайн».
3. Лист 1 переименовать в лист с названием Работа.
4. На рабочем листе «Работа» MS Excel создать таблицу базового прайс-листа на выполняемые работы.
5. Заполнить таблицу базового прайс-листа исходными данными (рисунок 1).

Рисунок 1. Структура таблицы «Прайс-лист» на рабочем листе Работа MS Excel

1. Лист 2 переименовать в лист с названием Расчет стоимости выполняемых работ;
2. Заполнить таблицу «Расчет стоимости выполняемых работ» исходными данными (рисунок 2);

Рисунок 2. Структура таблицы «Расчет стоимости выполняемых работ»

1. Заполнить графу Цена за ед. изм., руб. таблицы «Расчет стоимости выполняемых работ»
2. Занести в ячейку D3 формулу:

---

=ЕСЛИ(A3=Работа!A3;Работа!C3;ЕСЛИ(A3=Работа!A4;Работа!C4;ЕСЛИ(A3=Работа!A5;Работа!C5;ЕСЛИ(A3=Работа!A6;Работа!C6;ЕСЛИ(A3=Работа!A7;Работа!C7;ЕСЛИ(A3=Работа!A8;Работа!C8))))))

10. Размножить введенную в ячейку D2 формулу для остальных ячеек

(с D3 по D5) данной графы (рисунок 3);

Рисунок 3. Структура таблицы «Расчет стоимости выполняемых работ»

11. Заполнить графу Стоимость работ, руб. таблицы «Расчет стоимости выполняемых работ» следующим образом:

• • Занести в ячейку E3 формулу =C3*D3;
  • Размножить введенную в ячейку E3 формулу для остальных ячеек (с E4 по E6) данной графы;

12. Таблица «Расчет стоимости выполняемых работ» автоматически заполнится (рисунок 4.);

Рисунок 4. Структура таблицы «Расчет стоимости выполняемых работ»

13. Лист 3 переименовать в лист с названием Счет;

14. На рабочем листе «Счет» MS Excel создать форму счета на оплату выполненных работ (рисунок 5);

15. Путем создания межтабличных связей заполнить созданную форму полученными данными из таблицы «Расчет стоимости выполняемых работ»;

16. Заполнить графу ИТОГО формы счета на оплату выполненных работ следующим образом: в ячейку G16 ввести формулу =СУММ(G12:G15);

17. Заполнить графу НДС формы счета на оплату выполненных работ следующим образом: в ячейку G17 ввести формулу =G16*13%;

18. Заполнить графу СУММА С НДС формы счета на оплату выполненных работ следующим образом: в ячейку G18 ввести формулу =СУММ(G16:G17);

Рисунок 5. Структура таблицы «Счет»

19. Лист 4 переименовать в лист с названием График.

20. На рабочем листе «График» MS Excel создать сводную таблицу.

21. Путем создания межтабличных связей автоматически заполнить графы Наименование работы и Стоимость работ, руб. полученными данными из таблицы «Расчет стоимости выполняемых работ»

22. С помощью мастера диаграмм создать график.

23. Результаты вычислений представить графически (рисунок 6);

Рисунок 6. Сводная таблица и графическое представление результатов вычислений.

ЗАКЛЮЧЕНИЕ

Современную жизнь представить без современной техники просто невозможно.

Ни одна фирма не обходится без помощи компьютеров. Хранение данных, написание документов, составление графиков, таблиц, расписаний, создание презентаций - во всем в этом нам помогает компьютер, и помогает успешно.

---