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

Оглавление

Введение……………………………………………………………………….3

• Теоретическая часть…………………………………………………………5
1. Понятие алгоритма……………………………………………………..5
2. Оценка алгоритма сортировки………………………………………...6
3. Сортировка пузырьком………………………………………………...8
4. Сортировка перемешиванием…………………………………………9
5. Сортировка методом вставок………………………………………...10
6. Блочная сортировка…………………………………………………..11
7. Сортировка подсчетом………………………………………………..13
8. Сортировка слиянием………………………………………………...13
9. Двоичное дерево……………………………………………………...14
10. Цифровая сортировка………………………………………………...15
11. Гномья сортировка……………………………………………………15
12. Сортировка методом выбора…………………………………………16
13. Сортировка методом Шелла…………………………………………16
14. Сортировка расчёской………………………………………………..16
15. Пирамидальная сортировка………………………………………….17
16. Быстрая сортировка…………………………………………………..18
17. Блинная сортировка…………………………………………………..19
• Практическая часть………………………………………………………...20

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

Список использованной литературы……………………………………….28

 

 

 

 

 

 

 

 

Введение

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

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

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

Задача сортировки в  программировании не решена полностью.  Ведь,  хотя  и существует  большое  количество   алгоритмов   сортировки,   все же   целью программирования является не только разработка  алгоритмов  сортировки  элементов,  но и разработка именно эффективных алгоритмов сортировки. Мы знаем,   что  одну  и  ту же задачу можно решить с помощью разных алгоритмов, и каждый раз  изменение алгоритма приводит к новым, более или менее эффективным решениям   задачи. Основными требованиями к эффективности  алгоритмов  сортировки  является,  прежде всего, эффективность по времени и экономное использование памяти.  Согласно  этим  требованиям, простые алгоритмы  сортировки  (такие,  как  сортировка  выбором  и  сортировки включением) не являются очень эффективными.

Алгоритм сортировки обменами, хотя и завершает свою работу (поскольку он использует лишь циклы с параметром и в теле циклов параметры принудительно  не изменяются) и не использует вспомогательной  памяти,  но занимает  много  времени. Даже, если внутренний цикл не содержит ни одной перестановки, то  действия  будут повторяться до тех пор, пока не завершится внешний цикл.

Алгоритм  сортировки  выбором  более эффективная   сортировка   обменами   за критерием  М(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).

 

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

1.1 Понятие  алгоритма

 

Алгоритм – система  точно сформулированных правил, определяющих процесс преобразование доступных  исходных данных (входной информации) в желаемый результат (выходную информацию) за конечное число шагов [2, С 89].

Алгоритм обладает рядом свойств, связанных с необходимостью выполнения определенных требований к процессу вычисления. Это следующие свойства: 1) определённость; 2) массовость; 3) результативность; 4) дискретность. Определённость алгоритма означает,  что каждый шаг алгоритма должен быть точен, общепонятен, и исключать возможность различного толкования, другими словами алгоритм должен быть таким, чтобы его мог повторить любой пользователь. Массовость заключается в том, что алгоритм предназначен для решения целого класса задач, которые отличаются только своими входными условиями. Результативность означает, что пошаговый процесс решения задачи в соответствии с алгоритмом должен заканчиваться через определенное конечное число шагов.

Сортировка – один из наиболее распространенных процессов современной обработки данных. Сортировка - это процесс упорядочения некоторого множества элементов в некотором определенном порядке. Определенный порядок (например, упорядочение в алфавитном порядке, по возрастанию или убыванию количественных характеристик, по классам, типам и т.п.) в последовательности объектов необходимо для удобства работы с этим объектом [1, С 238 - 239]. Сортировка применяется во всех без исключения областях программирования, будь то базы данных или математические программы.

Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки [4,С 425]. На практике, в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.

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

Алгоритмы сортировки оцениваются  по скорости выполнения и эффективности  использования памяти:

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

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

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

Естественность  поведения — эффективность метода при обработке уже упорядоченных, или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.

Ещё одним важным свойством  алгоритма является его сфера  применения. Здесь основных типов  упорядочения две:

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

Внешняя сортировка оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (упорядочение файлов), т.е. в данный момент мы 'видим' только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью[3, С 214].

Алгоритмы сортировки данных

Список алгоритмов сортировки:

• Алгоритмы устойчивой сортировки:

• Сортировка пузырьком (Обменная сортировка)
• Сортировка перемешиванием (Сортировка коктейлем)
• Сортировка методом вставок
• Блочная сортировка (Корзинная сортировка)
• Сортировка подсчетом 
• Сортировка слиянием
• Двоичное древо 
• Цифровая сортировка (Сортировка по отделениям) 
• Поразрядная сортировка 
• Гномья сортировка

• Алгоритмы неустойчивой сортировки:

• Сортировка методом выбора 
• Сортировка методом Шелла 
• Сортировка расчёской
• Пирамидальная сортировка (Сортировка кучи) 
• Плавная сортировка
• Быстрая сортировка

• Непрактичные алгоритмы сортировки:

• Сортировка Акульшина
• Глупая сортировка
• Блинная сортировка

Существует множество  методов сортировки, каждый из которых  имеет свои достоинства и недостатки. Рассмотрим некоторые из них:

        1.3. Сортировка пузырьком

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис.1. Демонстрация сортировки по неубыванию методом "пузырька".

 

В пузырьковой сортировке количество сравнений всегда одно и то же, поскольку  два цикла for повторяются указанное количество раз независимо от того, был список изначально упорядочен или нет. Это значит, что алгоритм пузырьковой сортировки всегда выполняет 
сравнений, где n – количество сортируемых элементов. Данная формула выведена на том основании, что внешний цикл выполняется n-1 раз, а внутренний выполняется в среднем n/2 раз [3, С 217].

Пузырьковая сортировка имеет такую особенность: неупорядоченные  элементы на "большом" конце массива  занимают правильные положения за один проход, но неупорядоченные элементы в начале массива поднимаются на свои места очень медленно. Поэтому, вместо того чтобы постоянно просматривать массив в одном направлении, в последовательных проходах можно чередовать направления. Таким образом, элементы, сильно удаленные от своих положений, быстро станут на свои места. Данная версия пузырьковой сортировки носит название шейкер-сортировки (shaker sort сортировка перемешиванием, сортировка взбалтыванием, сортировка встряхиванием), поскольку действия, производимые ею с массивом, напоминают взбалтывание или встряхивание.

 

          1.4. Сортировка перемешиванием

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

 Анализируя метод  пузырьковой сортировки можно  отметить два обстоятельства.

Во-первых, если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, ее можно исключить из рассмотрения.

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

Эти две идеи приводят к следующим модификациям в методе пузырьковой сортировки. Границы рабочей части массива (т.е. части массива, где происходит движение) устанавливаются в месте последнего обмена на каждой итерации. Массив просматривается поочередно справа налево и слева направо.

 

1.5. Сортировка методом вставок

Простой алгоритм сортировки. Хотя этот метод сортировки намного менее эффективен, чем сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ:

• прост в реализации;
• эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;
• эффективен на наборах данных, которые уже частично отсортированы;
• это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);
• может сортировать массив по мере его получения;
• не требует временной памяти, даже под стек.

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

 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис.2. Демонстрация сортировки по неубыванию методом простого включения.

 

В отличие от пузырьковой  сортировки и сортировки простого выбора, количество сравнений в сортировке вставками зависит от изначальной упорядоченности списка. Если список уже отсортирован, количество сравнений равно n-1; в противном случае его производительность является величиной порядка n^2 [1, С 243 - 244].

 

1.6. Блочная сортировка

Блочная сортировка (Карманная сортировка, корзинная сортировка) — алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо иным другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем исполнения.

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

Алгоритм. Если входные  элементы подчиняются равномерному закону распределения, то математическое ожидание времени работы алгоритма карманной сортировки является линейным. Это возможно благодаря определенным предположениям о входных данных. При карманной сортировке предполагается, что входные данные равномерно распределены на отрезке [0, 1).

Идея алгоритма заключается  в том, чтобы разбить интервал [0, 1) на n одинаковых отрезков (карманов), и разделить по этим карманам n входных  величин. Поскольку входные числа  равномерно распределены, предполагается, что в каждый карман попадет небольшое количество чисел. Затем последовательно сортируются числа в карманах. Отсортированный массив получается путем последовательного перечисления элементов каждого кармана.

 

 

 

 

 

 

 

 

                     Рис.3. Элементы распределяются по корзинам

 

 

 

 

 

 

 

 

 

                  Рис.4. Затем элементы в каждой  корзине сортируются

 

 

 

 

         1.7. Сортировка подсчетом 

 

Один из самых простых (но и самых медленных) способов сортировки – это сортировка подсчетом. Этот метод подходит для сортировки целых чисел из не очень большого диапазона (сравнимого с размером массива). Для каждого элемента нужно найти, сколько элементов, меньших определенного числа, и поместить это число на соответствующие место. Делается это так: за линейный проход по массиву мы для каждого из возможных значений подсчитываем, сколько элементов имеют такое значение. Потом добавляем к каждому из найденных чисел суму всех предыдущих. Получая, таким образом, сколько есть элементов, значения которых не больше данного значения. Далее, опять-таки за линейный проход, формируем из исходного массива новый отсортированный. При этом следим, чтобы два одинаковых элемента не были записаны в одно место.

 

      1.8. Сортировка слиянием

 

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

Для решения задачи сортировки эти три этапа выглядят так:

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

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

 

         1.9. Двоичное дерево

 

Сортировка  с помощью двоичного дерева (сортировка двоичным деревом, сортировка деревом, древесная сортировка, сортировка с помощью бинарного дерева, англ. tree sort) - универсальный алгоритм сортировки, заключающийся в построении двоичного дерева поиска по ключам массива (списка), с последующей сборкой результирующего массива путём обхода узлов построенного дерева в необходимом порядке следования ключей. Данная сортировка является оптимальной при получении данных путём непосредственного чтения с потока (например с файла, сокета или консоли).

Алгоритм

1. Построение двоичного  дерева.

2. Сборка результирующего  массива путём обхода узлов  в необходимом порядке следования  ключей [7, С 4].

 

 

 

 

 

 

 

 

 

 

 

 

 

            Рис.5. Пример двоичного дерева

 

 

 

 

 

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

 

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

Этой сортировкой можно  сортировать целые неотрицательные  числа большого диапазона. Идея состоит  в следующем: отсортировать числа  по младшему разряду, потом устойчивой сортировкой сортируем по второму, третьему, и так до старшего разряда. В качестве устойчивой сортировки можно выбрать сортировку подсчетом, в виду малого времени работы.

 

         1.11. Гномья сортировка

 

Гномья сортировка (англ. Gnome sort) — алгоритм сортировки, похожий на сортировку вставками, но в отличие от последней перед вставкой на нужное место происходит серия обменов, как в сортировке пузырьком. Название происходит от предполагаемого поведения садовых гномов при сортировке линии садовых горшков.

Гномья сортировка основана на технике, используемой обычным голландским  садовым гномом. Это метод, которым  садовый гном сортирует линию  цветочных горшков. По существу он смотрит  на следующий и предыдущий садовые  горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил.

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

 

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

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

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

 

1.13 Сортировка методом Шелла

Основная идея этого  алгоритма заключается в устранении  массового беспорядка в массиве, сравнивая далеко стоящие друг от друга элементы. Интервал между сравниваемыми элементами постепенно уменьшается до единицы. Это означает, что на поздних стадиях сортировка сводится просто к перестановкам соседних элементов (если, конечно, такие перестановки являются необходимыми).

 

1.14. Сортировка расчёской

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

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

 

 1.15. Пирамидальная сортировка

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

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

-  каждый лист имеет  определенную глубину;

         -  значение в любой вершине больше, чем значения ее потомков.

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

 

 

 

 

1.16. Быстрая сортировка  

Быстрая сортировка - очень эффективный алгоритм, и известна как в среднем самая быстрая из универсальных алгоритмов сортировки. Быстрая сортировка сравнивает все элементы массива с одним, выбранным практически наугад, элементом (опорным элементом) и тем самым делит массив на две части - в одну попадают числа меньшие опорного, а в другую - большие опорного. Затем каждая из этих двух частей также подвергается аналогичной сортировке, и так до тех пор, пока очередная часть не окажется состоящей из единственного элемента.

Здесь интересен метод разделения массива относительно опорного элемента. Для этого используются два разнонаправленных  процесса. Первый начинает от начала массива  и ищет элемент, больший опорного. Второй начинает с конца и ищет элемент, меньший опорного. Как только такие элементы найдены, производится их обмен местами, и далее поиск продолжается с того места, где процессы остановились[8, С 3].