Экспериментальный анализ различных методов сортировки


 

Содержание:

1. Введение.

2. Цели работы.

3. Простые схемы сортировок.

4. Сортировка Шелла.

5. Сортировка деревом (пирамидальная сортировка) (Heapsort).

6. Быстрая сортировка (Quicksort).

7. Сортировка слиянием (Mergesort).

8. Поразрядная сортировка (Radixsort).

9. Сравнение работы сортировок на различных входных данных.

10. Заключение.

 

1. Введение.

Часто возникает необходимость упорядочить предметы по какому-то признаку: записать данные числа в порядке возрастания, слова — по алфавиту, людей выстроить по росту. Если можно сравнить любые два предмета из данного набора, то этот набор всегда можно упорядочить. Процесс упорядочивания информации и называют «сортировкой». Сортировка - это перестановка данных в соответствии с заданным образцом. Задачей алгоритма сортировки является перестройка первоначальной не отсортированной последовательности в отсортированную.

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

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

Время — основной параметр, характеризующий быстродействие алгоритма, также называется вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах мощности входного множества A. Если на вход алгоритму подаётся множество A, то обозначим n = |A|. Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — этоO(n^2). Идеальное поведение для упорядочения — O(n). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в Ω(n log n) сравнениях. Тем не менее, существует алгоритм сортировки Хана (Yijie Han) с вычислительной сложностью O(n log log n log log log n), использующий тот факт, что пространство ключей ограничено (он чрезвычайно сложен, а за О-обозначением скрывается весьма большой коэффициент, что делает невозможным его применение в повседневной практике). Также существует понятие сортирующих сетей. Предполагая, что можно одновременно (например, при параллельном вычислении) проводить несколько сравнений, можно отсортировать n чисел за O(log2 n) операций. При этом число n должно быть заранее известно.

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

У Алгоритмов сортировок  имеются определенные свойства и классификации:

1)Устойчивость (англ. stability) — устойчивая сортировка не меняет взаимного расположения элементов с одинаковыми ключами.

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

3) Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Минимальная трудоемкость худшего случая для этих алгоритмов составляет O(n log n), но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы.

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

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

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

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

Доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим.Объём данных не позволяет им разместиться в ОЗУ.

Также алгоритмы классифицируются по:

  • потребности в дополнительной памяти или её отсутствию
  • потребности в знаниях о структуре данных, выходящих за рамки операции сравнения, или отсутствию таковой

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

  • Сортировка массивов (внутренняя сортировка)
  • Сортировка последовательных файлов (внешняя сортировка)

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

Критериями оценки методов сортировки являются:

  • количество операций сравнения пар ключей
  • число перестановок элементов
  • экономное использование памяти.

В данной работе подробнее познакомимся с различными видами сортировок  и сравним их работу на разных входных данных.

2. Цели работы.

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

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

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

 

3. Простые схемы сортировок.

Для реализации я выбрала несколько простых сортировок: Сортировка «пузырьком» (BubbleSort) и Сортировка выбором (SelectionSort) и вставками, так как первой сортировкой я пользовалась на практике постоянно, а вторая и третья вызвали интерес в реализации на лекции. Рассмотрим каждую из них.

1)    Сортировка «пузырьком» (BubbleSort)

Сортировка пузырьком - самый естественный, он же самый медленный алгоритм сортировки. Массив чисел просматривается от начала до конца до тех пор, пока любые два рядом стоящих числа не будут расположены по возрастанию. Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. Для этого два, неверно расположенные одно относительно другого, числа меняются местами. При этом наименьшее число, как пузырёк, постепенно всплывает к началу массива (а наибольшее сразу "тонет" как камень). При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим наибольшим элементом, а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма). Время сортировки пузырьком растёт пропорционально квадрату роста количества элементов в массиве.

Следовательно получаем сложность алгоритма: O(n²). Лучшим случаем будет являться сложность - (O(n)),если массив данных уже будет у нас отсортирован. Худшим случаем у нас будет сложность - (O(n2)) – если массив будет упорядочен в обратном порядке, то есть по убыванию. Линейная сложность O(n)-если время будет возрастать прямо пропорционально количеству элементов и Квадратичная сложность  O(n2) . Время работы будет возрастать в квадратичной зависимости от количества элементов.

Проверим работу сортировки на различных входных данных, в зависимости от их количества и способа генерации:

 





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

 

2)Сортировка выбором (SelectionSort)

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

Алгоритм:

1)    находим номер минимального значения в текущем списке

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

3) сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы

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

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

Сортировка выбором предполагает n-1 перестановку, что делает этот алгоритм более эффективным для наихудшего случая, когда элементы исходного массива расположены в обратном порядке.  Минусом этой  сортировки является высокая сложность алгоритма:O(n²).Лучшим случаем будет-(O(n)) – если массив данных уже будет отсортирован. Худшим случаем будет-(O(n2)) –если массив будет  упорядочен в обратном порядке (по убыванию).

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

 

 

 

3) Сортировка вставками.

Сортировка вставками — примитивный алгоритм сортировки с высокой вычислительной сложностью: O(n²).

Плюсы:

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

Минусы:

  • Очень высокая вычислительная сложность алгоритма O(n²) (при использовании стандартного алгоритма).

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

Время выполнения алгоритма зависит от входных данных: чем большее множество нужно отсортировать, тем большее время выполняется сортировка. Также на время выполнения влияет исходная упорядоченность массива. Так, лучшим случаем является отсортированный массив, а худшим — массив, отсортированный в порядке, обратном нужному. Временная сложность алгоритма при худшем варианте входных данных — O(n²). Однако, данный алгоритм можно ускорить при помощи использования бинарного поиска для нахождения места текущему элементу в отсортированной части. Проблема с долгим сдвигом массива вправо решается при помощи смены указателей.

4. Сортировка Шелла.

Сортировка Шелла была названа в честь её изобретателя — Дональда Шелла, который опубликовал ее в 1959 году.

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

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

  • отсутствие потребности в памяти под стек;
  • отсутствие деградации при неудачных наборах данных — быстрая сортировка легко деградирует до O(n²), что хуже, чем худшее гарантированное время для сортировки Шелла.

Сортировка Шелла это, по сути, модификация схем сортировки других алгоритмов. Фактически для сортировки элементов используются другие алгоритмы, такие как: пузырьком, вставками, выбором и т.д. Но только эти алгоритмы применяются не ко всей исходной последовательности, а к ее частям.

Сначала в исходной последовательности сортируются между собой элементы, отстоящие друг от друга на расстоянии n/2 элементов, затем на расстоянии n/4 и т.д. до тех пор, пока не получим 2 последовательности, элементы которых отстоят друг от друга на расстоянии 1-го элемента. После этого делаем сортировку этой полученной последовательности выбранным методом и на выходе имеем уже полностью отсортированную последовательность. Сортировка Шелла (Shell sort) имеет сложность алгоритма: O(n log^2 n).

 

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

5. Сортировка деревом (пирамидальная сортировка) (Heapsort).

Сортировка пирамидой использует сортирующее дерево. Пирамидальная сортировка (англ. Heapsort, «Сортировка кучей») — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за О(n log n) операций при сортировке n-элементов. Количество применяемой служебной памяти не зависит от размера массива (то есть, O(1)).Может рассматриваться как усовершенствованная сортировка пузырьком, в которой элемент всплывает (min-heap) / тонет (max-heap) по многим путям.

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

Каждый лист имеет глубину либо d , либо d-1 , d,   — максимальная глубина дерева.

Значение в любой вершине не меньше (другой вариант — не больше) значения её потомков.

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

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

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

Array[i]≥Array[2i]

Array[i]≥Array[2i+1], при 1≤i≤n/2

Этот шаг требует O(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] — упорядоченная последовательность. Этот шаг требует O(n log n) операций.Ал­го­ритм пи­ра­ми­даль­ной сор­ти­ров­ки по-ан­глий­ски на­зы­ва­ет­ся «Heap Sort». «Heap» пе­ре­во­дит­ся, как «ку­ча». В свя­зи с этим пи­ра­ми­даль­ную сор­ти­ров­ку ещё на­зы­ва­ют «сор­ти­ров­ка ку­чей». Пи­ра­ми­да — дво­ич­ное де­ре­во, в ко­то­ром зна­че­ние каж­до­го эле­мен­та боль­ше ли­бо рав­но зна­че­ний до­чер­них эле­мен­тов.

 

За­пол­нив де­ре­во эле­мен­та­ми в про­из­воль­ном по­ряд­ке, мож­но лег­ко его от­сор­ти­ро­вать (лег­че, чем ис­ход­ный спи­сок эле­мен­тов), пре­вра­тив в пи­ра­ми­ду.

Са­мый боль­шой эле­мент пи­ра­ми­ды на­хо­дит­ся в её вер­ши­не.

От­де­ля­ем вер­шин­ный эле­мент, и за­пи­сы­ва­ем его в ко­нец ре­зуль­ти­рую­ще­го мас­си­ва. На ме­сто вер­шин­но­го эле­мен­та за­пи­сы­ва­ем эле­мент из са­мо­го ниж­не­го уров­ня де­ре­ва. Вос­ста­нав­ли­ва­ем (пе­ре­сор­ти­ро­вы­ва­ем) пи­ра­ми­ду.

 

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

 

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

 

Сложность: алгоритм работает в худшем, в среднем и в лучшем случае (то есть гарантированно) за O(nlogn) операций при сортировке n элементов.

 

 

 


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

 

6. Быстрая сортировка (Quicksort).

Быстрая сортировка (англ. quicksort), часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году. Один из самых быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов); из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.

QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка» и «Шейкерная сортировка»), известного, в том числе, своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате один из наиболее эффективных улучшенных методов.

Общая идея алгоритма состоит в следующем:

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

Быстрая сортировка использует стратегию «разделяй и властвуй». Поскольку в каждой итерации (на каждом следующем уровне рекурсии) длина обрабатываемого отрезка массива уменьшается, по меньшей мере, на единицу, терминальная ветвь рекурсии будет достигнута обязательно и обработка гарантированно завершится.

Оценка сложности алгоритма:

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

Лучший случай.

В наиболее сбалансированном варианте при каждой операции разделения массив делится на две почти одинаковые части, следовательно, максимальная глубина рекурсии, при которой размеры обрабатываемых подмассивов достигнут 1, составит log2n. В результате количество сравнений, делаемых быстрой сортировкой, было бы равно значению рекурсивного выражения Cn=2·Cn/2+n, что даёт общую сложность алгоритма O(n·log2n).

Среднее.

Среднюю сложность при случайном распределении входных данных можно оценить лишь вероятностно.

Прежде всего необходимо заметить, что в действительности необязательно, чтобы опорный элемент всякий раз делил массив на две одинаковых части. Например, если на каждом этапе будет происходить разделение на массивы длиной 75 % и 25 % от исходного, глубина рекурсии будет равна log4/3n, а это по-прежнему даёт сложность O(n·log n). Вообще, при любом фиксированном соотношении между левой и правой частями разделения сложность алгоритма будет той же, только с разными константами.

Будем считать «удачным» разделением такое, при котором опорный элемент окажется среди центральных 50 % элементов разделяемой части массива; ясно, вероятность удачи при случайном распределении элементов составляет 0,5. При удачном разделении размеры выделенных подмассивов составят не менее 25 % и не более 75 % от исходного. Поскольку каждый выделенный подмассив также будет иметь случайное распределение, все эти рассуждения применимы к любому этапу сортировки и любому исходному фрагменту массива.

Удачное разделение даёт глубину рекурсии не более log4/3n . Поскольку вероятность удачи равна 0,5, для получения k удачных разделений в среднем потребуется 2·k рекурсивных вызовов, чтобы опорный элемент kраз оказался среди центральных 50 % массива. Применяя эти соображения, можно заключить, что в среднем глубина рекурсии не превысит 2· log4/3n , что равно O(log n) . А поскольку на каждом уровне рекурсии по-прежнему выполняется не более O(n)  операций, средняя сложность составит O(n·log n) .

Худший случай.

В самом несбалансированном варианте каждое разделение даёт два подмассива размерами 1 и n-1 , то есть при каждом рекурсивном вызове больший массив будет на 1 короче, чем в предыдущий раз. Такое может произойти, если в качестве опорного на каждом этапе будет выбран элемент либо наименьший, либо наибольший из всех обрабатываемых. При простейшем выборе опорного элемента — первого или последнего в массиве, — такой эффект даст уже отсортированный (в прямом или обратном порядке) массив, для среднего или любого другого фиксированного элемента «массив худшего случая» также может быть специально подобран. В этом случае потребуется  операций разделения, а общее время работы составит Σni=0(n-i) = O(n2) операций, то есть сортировка будет выполняться за квадратичное время. Но количество обменов и, соответственно, время работы — это не самый большой его недостаток. Хуже то, что в таком случае глубина рекурсии при выполнении алгоритма достигнет n, что будет означать n-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов. Для больших значений n худший случай может привести к исчерпанию памяти (переполнению стека) во время работы программы.

 

Результат работы данной сортировки на разных входных данных, будет представлен в конце моей работы.

7. Сортировка слиянием (Mergesort).

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

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

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

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

3.1. Соединение двух упорядоченных массивов в один.

Основную идею слияния двух отсортированных массивов можно объяснить на следующем примере. Пусть мы имеем два уже отсортированных по возрастанию подмассива. Тогда:

3.2. Слияние двух подмассивов в третий результирующий массив. На каждом шаге мы берём меньший из двух первых элементов подмассивов и записываем его в результирующий массив. Счетчики номеров элементов результирующего массива и подмассива из которого был взят элемент увеличиваем на 1.

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

 

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

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

 

 

8. Поразрядная сортировка (Radixsort).

Алгоритм поразрядной сортировки использует совершенно иной подход сортировки элементов, позволяя в некоторых случаях достигать большей производительности и экономичности, чем другие алгоритмы. Особенность в том, что элементы непосредственно между собой, друг с другом, т.е. - не сравниваются. В двух словах: поразрядная сортировка подразумевает следующее: сначала элементы сортируются по своему младшему (последнему) разряду, затем следующему(предпоследнему) и т.д. до старшего разряда, первого. Поразрядная сортировка (Цифровая сортировка) — алгоритм сортировки за линейное время Алгоритм сортировки.
Числа сортируются по разрядам. Существует два варианта least significant digit (LSD) и most significant digit (MSD). При LSD сортировке, сначала сортируются младшие разряды, затем старшие. При MSD сортировке все наоборот. При LSD сортировке получается следующий порядок: короткие ключи идут раньше длинных, ключи одного размера сортируются по алфавиту, это совпадает с нормальным представлением чисел: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. При MSD сортировке получается алфавитный порядок, который подходит для сортировки строк. Например "b, c, d, e, f, g, h, i, j, ba" от сортируется как "b, ba, c, d, e, f, g, h, i, j". Если MSD применить к числам разной длины, то получим последовательность 1, 10, 2, 3, 4, 5, 6, 7, 8, 9.

При MSD сортировке последовательность сортируется по старшему значимому двоичному разряду так, чтобы все ключи, начинающиеся с 0 оказались перед всеми ключами начинающимися с 1. Для этого необходимо найти крайний слева ключ Ki, начинающийся с 1, и крайний справа ключ Kj, начинающийся с 0. После чего Ki и Kj меняются местами, и процесс повторяется, пока не получится i>j. Пусть F0 — множество элементов начинающихся с 0, F1 — множество всех остальных элементов. Применим к F0 поразрядную сортировку (начав теперь со второго бита слева, а не со старшего) до тех пор, пока множество F0 полностью не рассортируется. Затем проделаем то же самое с F1.




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

9. Сравнение работы сортировок на различных входных данных.

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

Варианты сравнения:

MT – используется метод «наибольший из двух»

AT – используется метод «средний из трёх»

 

 Из графиков наглядно видно, что самой быстрой для такого случая является Shellsort (Сортировка Шелла с промежутками Седжвика).

Посмотрим на время работы сортировок при количестве элементов порядка 50.

 

 Время работы сортировок при 500 элементах:

 

После сравнения работы на количестве элементов, равном 50 и 500,можно подвести некоторые итоги. Простые сортировки: вставками, пузырьком и выбором «выбывают из борьбы». Самой эффективной из них является InsertionSort. Shellsort (с промежутками Cеджвика) на данный момент начинает существенно отставать от Radixsort.

 

Рассмотрим поведение сортировок при работе на числах, сгруппированных по возрастанию.

 



10. Заключение.

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

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

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

Какие же результаты были получены при выполнении этого практического задания?

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

На основе результатов можно привести такие выводы:

Первое, это то, что «хорошая» оценка не гарантирует быстроту выполнения (Radixsort- Поразрядной сортировки).

Второй вывод: к «теоретической» оценке любого алгоритма можно «приближаться» вечно. То есть, любая оценка относительна («грубая») и на практике подобного результата просто трудно, а порой и невозможно достигнуть, но приближаться теоритической оценке всегда можно и нужно.

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

Также было выполнено теоретическое сравнение эффективности алгоритмов сортировок, рассматриваемых в рамках курсового проекта, построены соответствующие графики.

К данной работе прикреплен файл «Приложение», который содержит исходники программ, над которыми был проведен анализ.

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

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






ИЛИ