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

· прост в реализации

· эффективен на небольших наборах данных

· эффективен на наборах данных, которые уже частично отсортированы

· это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы)

· может сортировать список по мере его получения

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

Сортировка подсчётом

Сортировка подсчётом — алгоритм сортировки массива, при котором подсчитывается число одинаковых элементов. Алгоритм выгодно применять, когда в массиве много элементов, но все они достаточно малы.

англ. merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй».

Алгоритм был изобретён Джоном фон Нейманом в 1945 году.

Двоичное дерево (структура  данных)

Двоичное дерево — абстрактная структура данных, являющееся программной реализацией двоичного дерева (графа). Оно состоит из узлов (записей) вида (data, l, r), где data — некоторые данные привязанные к узлу, l, r — ссылки на узлы, являющиеся детьми данного узла. Узел l называется левым ребёнком, а узел r — правым.

Цифровая сортировка

Цифровая сортировка (англ. pigeonhole sort) обладает линейнойвычислительной сложностью (О(n)), что является лучшей возможной производительностью для алгоритма сортировки, так как в любом таком алгоритме каждый сортируемый элемент необходимо просмотреть хотя бы однажды. Однако, применение алгоритма цифровой сортировки целесообразно лишь тогда, когда сортируемые предметы имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым списком. Эффективность алгоритма падает всякий раз, когда несколько различных элементов попадает в одну ячейку. Необходимость сортировки внутри ячеек лишает алгоритм смысла, так как каждый элемент придётся просматривать более одного раза. Так что, для простоты и с целью отличить «классическую» цифровую сортировку от её многочисленных вариантов, укажем, что подсчёт должен быть обратимым: если два элемента попадают в одну ячейку, то они должны иметь одинаковое значение. Несколько элементов с одним значением в одной ячейке не портят картину — их можно просто вставить в отсортированный список рядом, один за другим (это позволяет применять цифровую сортировку в качестве устойчивой).

Алгоритм цифровой сортировки действует следующим образом:

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

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

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

Эффективность этого алгоритма  сильно зависит от плотности элементов  в массиве ячеек. Если элементов  этого массива намного больше, чем сортируемых предметов, то шаги 1 и 3 будут относительно медленными.

Сортировку подсчётом  применяют редко, потому что её требования редко удовлетворяются, и часто  бывает проще применить другие, более  гибкие и почти такие же быстрые  алгоритмы сортировки. В особенности, блочная сортировкаявляется более практичным вариантом сортировки подсчётом. В некотором роде,быстрая сортировка представляет собой обобщённую сортировку подсчётом (всего с двумя ячейками в каждый момент времени).

Поразрядная сортировка

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

Сортировка методом выбора

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

Алгоритм

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

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. Выполняется сортировка в каждой восьмерке. Наконец весь файл упорядочивается методом вставок. Поскольку дальние элементы уже переместились на свое место или находятся вблизи от него, этот этап будет значительно менее трудоемким, чем при сортировке вставками без предварительных «дальних» обменов.

Анализ алгоритма сортировки Шелла

Время выполнения сортировки пропорционально n1.2. Эта зависимость значительно лучше квадратичной

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

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

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

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(n2) сравнений. Обычно на практике быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(n log n), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре, и на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время.

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

Алгоритм

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

1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом.

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

3. Рекурсивно сортируем подсписки, лежащие слева и справа от опорного элемента.

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

Улучшения

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

Практическое задание  №7

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

1. Построить таблицы по приведенным в приложениях данным.

2. Выполнить расчет стоимости выполняемых работ по полученному заказу, данные расчета занести в таблицу (приложение 3).

3. Организовать межтабличные связи для автоматического формирования счета, выставляемого клиенту для оплаты выполняемых работ.

4. Сформировать и заполнить счет на оплату (приложение 4).

5. Результаты расчета стоимости каждого вида работ по полученному заказу представить в графическом виде (приложение 5).

Описание алгоритма выполнения практического задания

1. Запустить табличный процессор MS Excel;

2. Создать книгу с именем «Стройдизайн»;

3. Лист 1 переименовать в лист с названием Прайс-лист;

4. На рабочем листе Прайс-лист MS Excel создать таблицу базового прайс-листа;

5. Заполнить таблицу базового прайс-листа исходными данными;

6. Лист 2 переименовать в лист с названием Расчет стоимости выполняемых работ;

7. На рабочем листе Расчет стоимости выполняемых работ MS Excel создать таблицу, в которой будет содержаться объем выполняемых работ и их стоимость;

8. Заполнить таблицу Расчет стоимости выполняемых работ исходными данными;

9. Заполнить графу Цена за ед. изм., руб. таблицы Расчет стоимости выполняемых работ;

10. Занести в ячейку D3 формулу =ВПР(A3;Работы;3;ИСТИНА);

11. Размножить введенную в ячейку D2 формулу для остальных ячеек (с D3 поD5) данной графы;

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

· Занести в ячейку E3 формулу =C3*D3

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

13. Таблица Расчет стоимости выполняемых работ автоматически заполнится;

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

15. На рабочем листе Счет MS Excel создать форму счета на оплату выполненных работ;

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

17. Заполнить графу ИТОГО формы счета на оплату выполненных работ следующим образом: в ячейку G15 ввести формулу =G11+G12+G13+G14;

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

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

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

21. На рабочем листе График MS Excel создать график следующим образом

· Выделить таблицу Расчет стоимости выполняемых работ

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

Список используемой литературы

1. Программирование на языке высокого уровня: Текст лекций/ Н.В. Ефимушкина, С.П. Орлов, В.М. Чухонцев; Самар. гос. техн. ун-т. - Самара, 2002. 182с.

2. Экономическая информатика : В.П.Косарев/Л.В.Еремина, Москва, 2001.

3. Свободная энциклопедия «Википедия».

4. Сайт www. codelab.ru.

5. Сайт www.valera.asf.ru.

6. Сайт www. ru.wikipedia.org.

Приложение 1

Прайс-лист

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

Приложение 2

Расчет стоимости выполняемых  работ

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