Введение
В наше время новые информационные технологии занимают очень важное место не только в специализированных, но и в повседневных сферах жизни. Компьютеры применяются в бизнесе, менеджменте, торговле, учебе и многих других сферах деятельности человека.
Компьютерные технологии очень удобны для выполнения разнообразных операций, но в разных сферах применения эти операции разные. Потому, каждая отдельная отрасль, которая использует специфические технические средства, нуждается в своих собственных программах, которые обеспечивают работу компьютеров.
Разработкой программного обеспечения занимается такая отрасль науки, как программирование. Она приобретает все большее и большее значение в последнее время, ведь с каждым днем компьютер становится все более необходимым, все более повседневным явлением нашей жизни. Ведь вычислительная техника прошлых лет уже почти полностью исчерпала себя и не удовлетворяет тем потребностям, которые появляются перед человечеством.
Таким образом, новые информационные технологии очень актуальны в наше время и нуждаются в большем внимании для последующей разработки и совершенствования. Рядом с этим, большое значение имеет также и программирование, которое является одним из фундаментальных разделов информатики и потому не может оставаться в стороне.
Программирование содержит целый ряд важных внутренних задач. Одной из наиболее важных задач для программирования является задача сортировки. Под сортировкой обычно понимают перестановки элементов любой последовательности в определенном порядке. Эта задача является одной из важнейших потому, что ее целью является облегчение последующей обработки определенных данных и, в первую очередь, задачи поиска. Одним из эффективных алгоритмов поиска является бинарный поиск. Он работает быстрее, чем, например, линейный поиск, но его возможно применять лишь при условии, что последовательность уже упорядочена, то есть отсортирована.
Вообще, известно, что в любой сфере деятельности, которая использует компьютер для записи, обработки и сохранения информации, все данные сохраняются в базах данных, которые также нуждаются в сортировке. Определенная упорядоченность для них очень важна, ведь пользователю намного легче работать с данными, которые имеют определенный порядок.
Задача сортировки в программировании не решена полностью. Ведь, хотя и существует большое количество алгоритмов сортировки, все же целью программирования является не только разработка алгоритмов сортировки элементов, но и разработка именно эффективных алгоритмов сортировки. Мы знаем, что одну и ту же задачу можно решить с помощью разных алгоритмов, и каждый раз изменение алгоритма приводит к новым, более или менее эффективным решениям задачи. Основными требованиями к эффективности алгоритмов сортировки является, прежде всего, эффективность по времени и экономное использование памяти. Согласно этим требованиям, простые алгоритмы сортировки (такие, как сортировка выбором и сортировки включением) не являются очень эффективными.
Алгоритм сортировки обменами, хотя и завершает свою работу (поскольку он использует лишь циклы с параметром и в теле циклов параметры принудительно не изменяются) и не использует вспомогательной памяти, но занимает много времени. Даже, если внутренний цикл не содержит ни одной перестановки, то действия будут повторяться до тех пор, пока не завершится внешний цикл.
Алгоритм сортировки выбором более эффективная сортировка обменами за критерием М(n), то есть за количеством пересылок, но также является не очень эффективным. Из этих причин были разработаны некоторые новые алгоритмы сортировки, которые получили название быстрых алгоритмов сортировки. Это такие алгоритмы, как сортировка деревом, пирамидальная сортировка, быстрая сортировка Хоора и метод цифровой сортировки.
Целью теоретической части курсовой работы является ознакомление с алгоритмами сортировки, попытка проанализировать их и осветить каждый из них.
Краткие характеристики ПК и программного обеспечения, использованных для выполнения и оформления курсовой работы:
Процессор: INTEL PENTIUM 4 1.7 GHz;
Оперативная память: SD RAM 256mb;
Жесткий диск: HDD 40Gb;
Видеокарта: ATI RADEON 9600pro;
Клавиатура: Logitech G15;
Мышь: Logitech G9.
Программные средства: операционная система Windows ХР Professional sp2, пакет прикладных программ – MS Office 2003(из него использованы для выполнения курсовой работы: текстовый процессор MS Word 2003 табличный процессор MS Excel2003).
Алгоритмы сортировки
Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле по которому производится сортировка, называется ключом сортировки. На практике, в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.
Пожалуй, никакая другая проблема не породила такого количества разнообразнейших решений, как задача сортировки. Существует ли некий «универсальный», наилучший алгоритм? Вообще говоря, нет. Однако, имея приблизительные характеристики входных данных, можно подобрать метод, работающий оптимальным образом.
Оценка алгоритма сортировки
Для того, чтобы обоснованно сделать такой выбор, рассмотрим параметры, по которым будет производиться оценка алгоритмов.
Время сортировки — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для сортировки важны худшее, среднее и лучшее поведения алгоритма в терминах размера списка (n). Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — это ?(n²). Идеальное поведение для сортировки — O(n). Алгоритмы сортировки, которые используют только абстрактную операцию сравнения ключей, всегда нуждаются, по меньшей мере, в ?(n log n) сравнениях в среднем;
Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. При оценке используемой памяти не будет учитываться место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы.
Устойчивость (stability) — устойчивая сортировка не меняет взаимного расположения равных элементов. Такое свойство может быть очень полезным, если они состоят из нескольких полей, а сортировка происходит по одному из них.
Естественность поведения — эффективность метода при обработке уже отсортированных, или частично отсортированных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.
Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов сортировки две:
Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно сортируются на том же месте, без дополнительных затрат.
Внешняя сортировка оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (сортировка файлов), т.е в данный момент мы 'видим' только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам сортировки, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью.
доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим
объём данных не позволяет им разместиться в ОЗУ
Список алгоритмов сортировки
В этой таблице n — это количество записей, которые необходимо отсортировать, а k — это количество уникальных ключей.
Алгоритмы устойчивой сортировки
Сортировка пузырьком (англ. Bubble sort ) — сложность алгоритма: Q(n2); для каждой пары индексов производится обмен, если элементы расположены не по порядку
Сортировка перемешиванием (Сортировка коктейлем, Cocktail sort, bidirectional bubble sort) — Сложность алгоритма: O(n2)
Сортировка методом вставок (Insertion sort) — Сложность алгоритма: O(n2); определяем где текущий элемент должен находится в отсортированном списке и вставляем его туда
Блочная сортировка (Корзинная сортировка, Bucket sort) — Сложность алгоритма: O(n); требуется O(k) дополнительной памяти
Сортировка подсчетом (Counting sort) — Сложность алгоритма: O(n+k); требуется O(n+k) дополнительной памяти
Сортировка слиянием (Merge sort) — Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти; сортируем первую и вторую половину списка отдельно, а затем — сливаем отсортированные списки
In-place HYPERLINK "http://ru.wikipedia.org/w/index.php?title=Merge_sort&action=edit" \o "Merge sort" merge sort — Сложность алгоритма: O(n2)
Двоичное древо сортировки (Binary tree sort) — Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти
Цифровая сортировка (Сортировка по отделениям, Pigeonhole sort) — Сложность алгоритма: O(n+k); требуется O(k) дополнительной памяти
Поразрядная сортировка (Radix sort) — Сложность алгоритма: O(n·k); требуется O(n) дополнительной памяти
сортирует строки буква за буквой
Гномья сортировка (Gnome sort) — Сложность алгоритма: O(n2)
Алгоритмы неустойчивой сортировки
HYPERLINK "http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%B0" \o "Сортировка методом выбора" Сортировка методом выбора (Selection sort) — Сложность алгоритма: O(n2); поиск наименьшего или наибольшего элемента и помещения его в начало или конец отсортированного списка
HYPERLINK "http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%A8%D0%B5%D0%BB%D0%BB%D0%B0" \o "Сортировка методом Шелла" Сортировка методом Шелла (Shell sort) — Сложность алгоритма: O(n log n); попытка улучшить сортировку вставками
HYPERLINK "http://ru.wikipedia.org/w/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D1%80%D0%B0%D1%81%D1%87%D1%91%D1%81%D0%BA%D0%BE%D0%B9&action=edit" \o "Сортировка расчёской" Сортировка расчёской (Comb sort) — Сложность алгоритма: O(n log n)
HYPERLINK "http://ru.wikipedia.org/wiki/%D0%9F%D0%B8%D1%80%D0%B0%D0%BC%D0%B8%D0%B4%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0" \o "Пирамидальная сортировка" Пирамидальная сортировка (Сортировка кучи, Heapsort) — Сложность алгоритма: O(n log n); превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка
HYPERLINK "http://ru.wikipedia.org/w/index.php?title=%D0%9F%D0%BB%D0%B0%D0%B2%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0&action=edit" \o "Плавная сортировка" Плавная сортировка (Smoothsort) — Сложность алгоритма: O(n log n)
HYPERLINK "http://ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0" \o "Быстрая сортировка" Быстрая сортировка (Quicksort) — Сложность алгоритма: O(n log n) — среднее время, O(n2) — худший случай; широко известен как быстрейший из известных для сортировки больших случайных списков; с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине
HYPERLINK "http://ru.wikipedia.org/w/index.php?title=Introsort&action=edit" \o "Introsort" Introsort — Сложность алгоритма: O(n log n)
HYPERLINK "http://ru.wikipedia.org/w/index.php?title=Patience_sorting&action=edit" \o "Patience sorting" Patience sorting — Сложность алгоритма: O(n log n + k) — наихудший случай, требует дополнительно O(n + k) памяти, также находит HYPERLINK "http://ru.wikipedia.org/w/index.php?title=%D0%A1%D0%B0%D0%BC%D0%B0%D1%8F_%D0%B4%D0%BB%D0%B8%D0%BD%D0%BD%D0%B0%D1%8F_%D1%83%D0%B2%D0%B5%D0%BB%D0%B8%D1%87%D0%B8%D0%B2%D0%B0%D1%8E%D1%89%D0%B0%D1%8F%D1%81%D1%8F_%D0%BF%D0%BE%D0%B4%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D1%8C&action=edit" \o "Самая длинная увеличивающаяся подпоследовательность" самую длинную увеличивающуюся подпоследовательность
Непрактичные алгоритмы сортировки
HYPERLINK "http://ru.wikipedia.org/w/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%90%D0%BA%D1%83%D0%BB%D1%8C%D1%88%D0%B8%D0%BD%D0%B0&action=edit" \o "Сортировка Акульшина" Сортировка Акульшина (Akulshin sort) — O(n × n!) — худшее время. Генерируем всевозможные перестановки исходного массива и для каждой осуществдяем проверку верной отсортированности.
HYPERLINK "http://ru.wikipedia.org/w/index.php?title=%D0%93%D0%BB%D1%83%D0%BF%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0&action=edit" \o "Глупая сортировка" Глупая сортировка (Stupid sort) — O(n3); рекурсивная версия требует дополнительно O(n2) памяти
HYPERLINK "http://ru.wikipedia.org/w/index.php?title=Bead_Sort&action=edit" \o "Bead Sort" Bead Sort — O(n) or O(vn), требуется специализированное железо
HYPERLINK "http://ru.wikipedia.org/w/index.php?title=%D0%91%D0%BB%D0%B8%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0&action=edit" \o "Блинная сортировка" Блинная сортировка (Pancake sorting) — O(n), требуется специализированное железо
Сортировка пузырьком
Сортиро?вка пузырько?м ( HYPERLINK "http://ru.wikipedia.org/wiki/%D0%90%D0%BD%D0%B3%D0%BB%D0%B8%D0%B9%D1%81%D0%BA%D0%B8%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA" \o "Английский язык" англ. bubble sort) — простой HYPERLINK "http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8" \o "Алгоритм сортировки" алгоритм сортировки. Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.
Сортировка методом пузырька имеет сложность O(n2). Для понимания и реализации это — простейший алгоритм сортировки, но эффективен он лишь для небольших массивов.
Пример реализации алгоритма (язык HYPERLINK "http://ru.wikipedia.org/wiki/Pascal" \o "Pascal" Pascal):
for i := n - 1 downto 1 do
for j := 1 to i do
if a[j] > a[j+1] then
begin
t := a[j];
a[j] := a[j+1];
a[j+1] := t;
end;
Сортировка перемешиванием
Сортировка перемешиванием (шейкер-сортировка) — разновидность HYPERLINK "http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%BF%D1%83%D0%B7%D1%8B%D1%80%D1%8C%D0%BA%D0%BE%D0%BC" \o "Сортировка пузырьком" пузырьковой сортировки. Отличается тем, что просмотры элементов выполняются один за другим в противоположных направлениях, при этом большие элементы стремятся к концу массива, а маленькие — к началу.
Лучший случай для этой сортировки — отсортированный массив (О(n)), худший — отсортированный в обратном порядке (O(n²)).
Сортировка методом вставок
Сортировка методом вставок ( HYPERLINK "http://ru.wikipedia.org/wiki/%D0%90%D0%BD%D0%B3%D0%BB%D0%B8%D0%B9%D1%81%D0%BA%D0%B8%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA" \o "Английский язык" англ. insertion sort) — простой HYPERLINK "http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8" \o "Алгоритм сортировки" алгоритм сортировки. Хотя этот метод сортировки намного менее эффективен чем более сложные алгоритмы (такие как HYPERLINK "http://ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0" \o "Быстрая сортировка" быстрая сортировка), у него есть ряд преимуществ:
прост в реализации
эффективен на небольших наборах данных
эффективен на наборах данных, которые уже частично отсортированы
это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы)
может сортировать список по мере его получения
На каждом шаге алгоритма, мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор пока набор входных данных не будет исчерпан. Выбор очередного элемента, выбираемого из исходного массива — произволен, может использоваться практически любой алгоритм выбора.
Сортировка подсчётом
Сортировка подсчётом — HYPERLINK "http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8" \o "Алгоритм сортировки" алгоритм сортировки HYPERLINK "http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%81%D1%81%D0%B8%D0%B2" \o "Массив" массива, при котором подсчитывается число одинаковых элементов. Алгоритм выгодно применять, когда в массиве много элементов, но все они достаточно малы.
Описание алгоритма
Идея сортировки указана в её названии — нужно подсчитывать число элементов, а затем выстраивать массив. Пусть, к примеру, имеется массив A из миллиона натуральных чисел, меньших 100. Тогда можно создать вспомогательный массив B из 99 (1..99) элементов, «пробежать» весь исходный массив и вычислять частоту встречаемости каждого элемента — то есть если A[i]=a, то B[a] следует увеличить на единицу. Затем «пробежать» счетчиком i массив B, записывая в массив A число i B[i] раз.
Сортировка слиянием
Сортировка слиянием ( HYPERLINK "http://ru.wikipedia.org/wiki/%D0%90%D0%BD%D0%B3%D0%BB%D0%B8%D0%B9%D1%81%D0%BA%D0%B8%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA" \o "Английский язык" англ. merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа HYPERLINK "http://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B7%D0%B4%D0%B5%D0%BB%D1%8F%D0%B9_%D0%B8_%D0%B2%D0%BB%D0%B0%D1%81%D1%82%D0%B2%D1%83%D0%B9" \o "Разделяй и властвуй" «разделяй и властвуй».
Алгоритм был изобретён HYPERLINK "http://ru.wikipedia.org/wiki/%D0%A4%D0%BE%D0%BD_%D0%9D%D0%B5%D0%B9%D0%BC%D0%B0%D0%BD%2C_%D0%94%D0%B6%D0%BE%D0%BD" \o "Фон Нейман, Джон" Джоном фон Нейманом в HYPERLINK "http://ru.wikipedia.org/wiki/1945" \o "1945" 1945 году.
Двоичное дерево (структура данных)
Двоичное дерево — абстрактная структура данных, являющееся программной реализацией HYPERLINK "http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%28%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2%29" \l ".D0.94.D0.B2.D0.BE.D0.B8.D1.87.D0.BD.D0.BE.D0.B5_.D0.B4.D0.B5.D1.80.D0.B5.D0.B2.D0.BE" \o "Дерево (теория графов)" двоичного дерева (графа). Оно состоит из узлов (записей) вида (data, l, r), где data — некоторые данные привязанные к узлу, l, r — ссылки на узлы, являющиеся детьми данного узла. Узел l называется левым ребёнком, а узел r — правым.
Цифровая сортировка
Цифровая сортировка ( HYPERLINK "http://ru.wikipedia.org/wiki/%D0%90%D0%BD%D0%B3%D0%BB%D0%B8%D0%B9%D1%81%D0%BA%D0%B8%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA" \o "Английский язык" англ. pigeonhole sort) обладает линейной HYPERLINK "http://ru.wikipedia.org/w/index.php?title=%D0%92%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C&action=edit" \o "Вычислительная сложность" вычислительной сложностью (О(n)), что является лучшей возможной производительностью для HYPERLINK "http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8" \o "Алгоритм сортировки" алгоритма сортировки, так как в любом таком алгоритме каждый сортируемый элемент необходимо просмотреть хотя бы однажды. Однако, применение алгоритма цифровой сортировки целесообразно лишь тогда, когда сортируемые предметы имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым списком. Эффективность алгоритма падает всякий раз, когда несколько различных элементов попадает в одну ячейку. Необходимость сортировки внутри ячеек лишает алгоритм смысла, так как каждый элемент придётся просматривать более одного раза. Так что, для простоты и с целью отличить «классическую» цифровую сортировку от её многочисленных вариантов, укажем, что подсчёт должен быть обратимым: если два элемента попадают в одну ячейку, то они должны иметь одинаковое значение. Несколько элементов с одним значением в одной ячейке не портят картину — их можно просто вставить в отсортированный список рядом, один за другим (это позволяет применять цифровую сортировку в качестве HYPERLINK "http://ru.wikipedia.org/wiki/%D0%A3%D1%81%D1%82%D0%BE%D0%B9%D1%87%D0%B8%D0%B2%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0" \o "Устойчивая сортировка" устойчивой).
Алгоритм цифровой сортировки действует следующим образом:
Создаём массив изначально пустых «ячеек», по одной для каждой величины из диапазона ключей.
Просматриваем изначальный массив, помещая каждый его элемент в свою ячейку.
Проходим по массиву ячеек в нужном порядке и переносим элементы из непустых ячеек обратно в первоначальный массив.
Эффективность этого алгоритма сильно зависит от плотности элементов в массиве ячеек. Если элементов этого массива намного больше, чем сортируемых предметов, то шаги 1 и 3 будут относительно медленными.
Сортировку подсчётом применяют редко, потому что её требования редко удовлетворяются, и часто бывает проще применить другие, более гибкие и почти такие же быстрые алгоритмы сортировки. В особенности, HYPERLINK "http://ru.wikipedia.org/w/index.php?title=%D0%91%D0%BB%D0%BE%D1%87%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0&action=edit" \o "Блочная сортировка" блочная сортировка является более практичным вариантом сортировки подсчётом. В некотором роде, HYPERLINK "http://ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0" \o "Быстрая сортировка" быстрая сортировка представляет собой обобщённую сортировку подсчётом (всего с двумя ячейками в каждый момент времени).
Поразрядная сортировка
Поразрядная сортировка — быстрая устойчивая сортировка за линейное время, использовалась в устройствах для сортировки HYPERLINK "http://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D1%84%D0%BE%D0%BA%D0%B0%D1%80%D1%82%D0%B0" \o "Перфокарта" перфокарт. Пригодна для сортировки любых элементов, состоящих из цепочек над фиксированным HYPERLINK "http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D1%84%D0%B0%D0%B2%D0%B8%D1%82" \o "Алфавит" алфавитом, на котором задано отношение сравнения. Для сортировки следует применять любой устойчивый HYPERLINK "http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC" \o "Алгоритм" алгоритм, используя в качестве ключа сначала младшую букву, затем повторять этот процесс для старших букв.
Сортировка методом выбора
Сортировка методом выбора ( HYPERLINK "http://ru.wikipedia.org/wiki/%D0%90%D0%BD%D0%B3%D0%BB%D0%B8%D0%B9%D1%81%D0%BA%D0%B8%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA" \o "Английский язык" англ. selection sort) — HYPERLINK "http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8" \o "Алгоритм сортировки" алгоритм сортировки, относящийся к неустойчивым алгоритмам сортировки. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае HYPERLINK "http://ru.wikipedia.org/w/index.php?title=O-%D1%81%D0%B8%D0%BC%D0%B2%D0%BE%D0%BB%D0%B8%D0%BA%D0%B0&action=edit" \o "O-символика" ?(n2), предполагая, что сравнения делаются за постоянное время.
Алгоритм
Шаги алгоритма:
находим минимальное значение в текущем списке
производим обмен этого значения со значением на первой позиции
теперь сортируем хвост списка, исключив из рассмотрения уже отсортированный первый элемент
HYPERLINK "http://ru.wikipedia.org/wiki/%D0%9F%D0%B8%D1%80%D0%B0%D0%BC%D0%B8%D0%B4%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0" \o "Пирамидальная сортировка" Пирамидальная сортировка сильно улучшает базовый алгоритм, используя структуру данных HYPERLINK "http://ru.wikipedia.org/wiki/%D0%9A%D1%83%D1%87%D0%B0" \o "Куча" ключа для ускорения нахождения и удаления минимального элемента.
Существует также двунаправленный вариант сортировки методом вставок, в котором на каждом проходе отыскивается и устанавливается на своё место и минимальное, и максимальное значения.
Сортировка методом Шелла
Идея алгоритма состоит в обмене элементов, расположенных не только рядом, как в HYPERLINK "http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%B2%D1%81%D1%82%D0%B0%D0%B2%D0%BE%D0%BA" \o "Сортировка методом вставок" сортировке методом вставок, но и далеко друг от друга, что значительно сокращает общее число операций перемещения элементов.
Для примера возьмем HYPERLINK "http://ru.wikipedia.org/wiki/%D0%A4%D0%B0%D0%B9%D0%BB" \o "Файл" файл из 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. Выполняется сортировка в каждой восьмерке. Наконец весь файл упорядочивается HYPERLINK "http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%B2%D1%81%D1%82%D0%B0%D0%B2%D0%BE%D0%BA" \o "Сортировка методом вставок" методом вставок. Поскольку дальние элементы уже переместились на свое место или находятся вблизи от него, этот этап будет значительно менее трудоемким, чем при сортировке вставками без предварительных «дальних» обменов.
Анализ алгоритма сортировки Шелла
Время выполнения сортировки пропорционально n1.2. Эта зависимость значительно лучше квадратичной зависимости n2, которой подчиняется большинство простых алгоритмов сортировки.
Пример реализации
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 элементов.
Алгоритм
HYPERLINK "http://ru.wikipedia.org/wiki/%D0%98%D0%B7%D0%BE%D0%B1%D1%80%D0%B0%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5:%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D1%83%D1%8E%D1%89%D0%B5%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE.GIF" \o " пример сортирующего дерева " Сортировка пирамидой использует HYPERLINK "http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D1%83%D1%8E%D1%89%D0%B5%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" \o "Сортирующее дерево" сортирующее дерево. Сортирующее дерево – это такое двоичное дерево, у которого выполнены условия:
Каждый лист имеет глубину либо d либо d-1
Значение в любой вершине больше, чем значения ее потомков.
HYPERLINK "http://ru.wikipedia.org/wiki/%D0%98%D0%B7%D0%BE%D0%B1%D1%80%D0%B0%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5:%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D1%83%D1%8E%D1%89%D0%B5%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D1%80%D0%B0%D0%B7%D0%B2%D0%B5%D1%80%D0%BD%D1%83%D1%82%D0%BE%D0%B5_%D0%B2_%D0%BC%D0%B0%D1%81%D1%81%D0%B8%D0%B2.GIF" \o "структура данных для хранения сортирующего дерева" Удобная структура данных для сортирующего дерева – такой массив Array, что Array[1] – элемент в корне, а потомки элемента Array[i] - Array[2i] и Array[2i+1].
Алгоритм сортировки будет состоять из двух основных шагов:
1. Выстраиваем элементы массива в виде сортирующего дерева:
INCLUDEPICTURE "http://upload.wikimedia.org/math/0/c/1/0c195b642477785e6de79e2c936db87a.png" \* MERGEFORMATINET
INCLUDEPICTURE "http://upload.wikimedia.org/math/2/9/2/29226cd812334a62639271af0ef5837b.png" \* MERGEFORMATINET
при INCLUDEPICTURE "http://upload.wikimedia.org/math/a/e/2/ae2fc63586763b459056a291052f5380.png" \* MERGEFORMATINET
Этот шаг требует О(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) операций.
Быстрая сортировка
Быстрая сортировка ( HYPERLINK "http://ru.wikipedia.org/wiki/%D0%90%D0%BD%D0%B3%D0%BB%D0%B8%D0%B9%D1%81%D0%BA%D0%B8%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA" \o "Английский язык" англ. quicksort) — широко известный HYPERLINK "http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8" \o "Алгоритм сортировки" алгоритм сортировки, разработанный английским информатиком HYPERLINK "http://ru.wikipedia.org/wiki/%D0%A5%D0%BE%D0%B0%D1%80%2C_%D0%A7%D0%B0%D1%80%D0%BB%D1%8C%D0%B7_%D0%AD%D0%BD%D1%82%D0%BE%D0%BD%D0%B8_%D0%A0%D0%B8%D1%87%D0%B0%D1%80%D0%B4" \o "Хоар, Чарльз Энтони Ричард" Чарльзом Хоаром. Даёт в среднем O(n log n) сравнений при сортировке n элементов. В худшем случае, однако, получается O(n2) сравнений. Обычно на практике быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(n log n), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре, и на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время.
Интересно, что Хоар разработал этот метод применительно к HYPERLINK "http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%BD%D1%8B%D0%B9_%D0%BF%D0%B5%D1%80%D0%B5%D0%B2%D0%BE%D0%B4" \o "Машинный перевод" машинному переводу: дело в том, что в то время словарь хранился на HYPERLINK "http://ru.wikipedia.org/w/index.php?title=%D0%9C%D0%B0%D0%B3%D0%BD%D0%B8%D1%82%D0%BD%D0%B0%D1%8F_%D0%BB%D0%B5%D0%BD%D1%82%D0%B0&action=edit" \o "Магнитная лента" магнитной ленте, и если отсортировать все слова в тексте, их переводы можно получить за один прогон ленты.
Алгоритм
Быстрая сортировка использует стратегию HYPERLINK "http://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B7%D0%B4%D0%B5%D0%BB%D1%8F%D0%B9_%D0%B8_%D0%B2%D0%BB%D0%B0%D1%81%D1%82%D0%B2%D1%83%D0%B9" \o "Разделяй и властвуй" «разделяй и властвуй». Шаги алгоритма таковы:
Выбираем в массиве некоторый элемент, который будем называть опорным элементом.
Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него.
Рекурсивно сортируем подсписки, лежащие слева и справа от опорного элемента.
Базой рекурсии являются списки, состоящие из одного или двух элементов, которые уже отсортированы. Алгоритм всегда завершается, поскольку за каждую итерацию он ставит по крайней мере один элемент на его окончательное место.
Улучшения
При выборе опорного элемента из данного диапазона случайным образом, худший случай становится очень маловероятным и ожидаемое время выполнения алгоритма сортировки - O(n log n).
Практическое задание №7
Фирма ООО «Стройдизайн» осуществляет деятельность, связанную с выполнением работ по ремонту помещений. Прайс-лист на выполняемые работы приведен в приложении 1. Данные о заказанных работах указаны в приложении 2.
Построить таблицы по приведенным в приложениях данным.
Выполнить расчет стоимости выполняемых работ по полученному заказу, данные расчета занести в таблицу (приложение 3).
Организовать межтабличные связи для автоматического формирования счета, выставляемого клиенту для оплаты выполняемых работ.
Сформировать и заполнить счет на оплату (приложение 4).
Результаты расчета стоимости каждого вида работ по полученному заказу представить в графическом виде (приложение 5).
Описание алгоритма выполнения практического задания
Запустить табличный процессор MS Excel;
Создать книгу с именем «Стройдизайн»;
Лист 1 переименовать в лист с названием Прайс-лист;
На рабочем листе Прайс-лист MS Excel создать таблицу базового прайс-листа;
Заполнить таблицу базового прайс-листа исходными данными;
Лист 2 переименовать в лист с названием Расчет стоимости выполняемых работ;
На рабочем листе Расчет стоимости выполняемых работ MS Excel создать таблицу, в которой будет содержаться объем выполняемых работ и их стоимость;
Заполнить таблицу Расчет стоимости выполняемых работ исходными данными;
Заполнить графу Цена за ед. изм., руб. таблицы Расчет стоимости выполняемых работ;
Занести в ячейку D3 формулу =ВПР(A3;Работы;3;ИСТИНА);
Размножить введенную в ячейку D2 формулу для остальных ячеек (с D3 по D5) данной графы;
Заполнить графу Стоимость работ, руб. таблицы Расчет стоимости выполняемых работ следующим образом:
Занести в ячейку E3 формулу =C3*D3
Размножить введенную в ячейку E3 формулу для остальных ячеек (с E4 по E6) данной графы
Таблица Расчет стоимости выполняемых работ автоматически заполнится;
Лист 3 переименовать в лист с названием Счет;
На рабочем листе Счет MS Excel создать форму счета на оплату выполненных работ;
Путем создания межтабличных связей заполнить созданную форму полученными данными из таблицы Расчет стоимости выполняемых работ;
Заполнить графу ИТОГО формы счета на оплату выполненных работ следующим образом: в ячейку G15 ввести формулу =G11+G12+G13+G14;
Заполнить графу НДС формы счета на оплату выполненных работ следующим образом: в ячейку G16 ввести формулу =G15*18/100;
Заполнить графу СУММА С НДС формы счета на оплату выполненных работ следующим образом: в ячейку G17 ввести формулу =G15+G16;
Лист 4 переименовать в лист с названием График;
На рабочем листе График MS Excel создать график следующим образом
Выделить таблицу Расчет стоимости выполняемых работ
С помощью мастера диаграмм создать график.
Список используемой литературы
Программирование на языке высокого уровня: Текст лекций/ Н.В. Ефимушкина, С.П. Орлов, В.М. Чухонцев; Самар. гос. техн. ун-т. - Самара, 2002. 182с.
Экономическая информатика : В.П.Косарев/Л.В.Еремина, Москва, 2001.
Свободная энциклопедия «Википедия».
Сайт www. codelab.ru.
Сайт www.valera.asf.ru.
Сайт www. ru.wikipedia.org.
