Типы сортировки данных. Алгортим "Сортировка слиянием". Понятие быстрой сортировки

МЕТОДЫ СОРТИРОВКИ

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

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

Пример. Отсортировать элементы одномерного массива целых чисел по возрастанию.

На рисунке 1 приведена последовательность перестановки элементов.

Рисунок 1. Сортировка методом «пузырька»

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

На рисунке 2 приведена блок-схема рассмотренного алгоритма.

Рисунок 2. Блок-схема алгоритма сортировки методом «пузырька»

Переменная m введена для возможности обмена значениями между двумя переменными, k отвечает за шаги сортировки.

Программа на языке С++ по данному алгоритму будет выглядеть следующим образом.

Рисунок 3. Программа сортировки элементов массива методом «пузырька»

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

Более эффективным является метод прямого выбора

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

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

сортировка значение программный обеспечение

Рисунок 4. Сортировка методом прямого выбора

Фрагмент программы, с помощью которого реализуется сортировка методом прямого выбора, приведен ниже.

// сортируем элементы массива по возрастанию

int temp;//переменная для временного хранения при обмене значениями

int i;//переменная управления циклом (номер элемента массива)

int k;//переменная управления циклом (номер шага сортировки)

int nmin;//номер минимального значения

for (к=0; i < к 1; i++)

// ищем номер минимального элемента среди значений list [ i … n -1]

for (i = k+1; i< n; i++)

if (list[i] < list[ nmin ]) nmin = i;

//меняем местами list[ nmin ] и list[ k ]

temp = list[ nmin ];

list[ nmin ]= list[ k ];

list[ k ] = temp;

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

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

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

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

Классификация алгоритмов сортировки

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

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

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

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

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

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

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

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

Сортировка пузырьком (англ. Bubble sort ) - сложность алгоритма: O(n 2) ; для каждой пары индексов производится обмен, если элементы расположены не по порядку.
Сортировка перемешиванием (Шейкерная, Cocktail sort, bidirectional bubble sort) - Сложность алгоритма: O(n 2)
Сортировка вставками (Insertion sort) - Сложность алгоритма: O(n 2); определяем где текущий элемент должен находиться в упорядоченном списке и вставляем его туда
Блочная сортировка (Корзинная сортировка, Bucket sort) - Сложность алгоритма: O(n ); требуется O(k ) дополнительной памяти и знание о природе сортируемых данных, выходящее за рамки функций "переставить" и "сравнить".
Сортировка подсчётом (Counting sort) - Сложность алгоритма: O(n +k ); требуется O(n +k ) дополнительной памяти (рассмотрено 3 варианта)
Сортировка слиянием (Merge sort) - Сложность алгоритма: O(n log n ); требуется O(n ) дополнительной памяти; выстраиваем первую и вторую половину списка отдельно, а затем - сливаем упорядоченные списки
In-place merge sort - Сложность алгоритма: O(n 2), O(n log 2 n ) или O(n log n ) в зависимости от применяемого алгоритма слияния.
Двоичное дерево сортировки (Binary tree sort) - Сложность алгоритма: O(n log n ); требуется O(n ) дополнительной памяти
Цифровая сортировка (Сортировка по отделениям, Pigeonhole sort) - Сложность алгоритма: O(n +k ); требуется O(k ) дополнительной памяти
Гномья сортировка (Gnome sort) - Сложность алгоритма: O(n 2)

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

Сортировка выбором (Selection sort) - Сложность алгоритма: O(n 2); поиск наименьшего или наибольшего элемента и помещения его в начало или конец упорядоченного списка
Сортировка Шелла (Shell sort) - Сложность алгоритма: O(n log 2 n ); попытка улучшить сортировку вставками
Сортировка расчёской (Comb sort) - Сложность алгоритма: O(n log n )
Пирамидальная сортировка (Сортировка кучи, Heapsort) - Сложность алгоритма: O(n log n ); превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка
Плавная сортировка (Smoothsort) - Сложность алгоритма: O(n log n )
Быстрая сортировка (Quicksort) - Сложность алгоритма: O(n log n ) - среднее время, O(n 2) - худший случай; широко известен как быстрейший из известных для упорядочения больших случайных списков; с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине
Introsort - Сложность алгоритма: O(n log n ), сочетание быстрой и пирамидальной сортировки. Пирамидальная сортировка применяется в случае, если глубина рекурсии превышает log(n).
Patience sorting - Сложность алгоритма: O(n log n + k ) - наихудший случай, требует дополнительно O(n + k ) памяти, также находит самую длинную увеличивающуюся подпоследовательность
Обменная поразрядная сортировка - Сложность алгоритма: O(n ·k ); требуется O(k ) дополнительной памяти

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

Bogosort - O(n ·n !) в среднем. Произвольно перемешать массив, проверить порядок.
Сортировка перестановкой - O(n ·n !) - худшее время. Генерируются всевозможные перестановки исходного массива и для каждой осуществляется проверка верного порядка.
Глупая сортировка (Stupid sort) - O(n 3); рекурсивная версия требует дополнительно O(n 2) памяти
Bead Sort - O(n ) or O(√n
Блинная сортировка (Pancake sorting) - O(n ), требуется специализированное аппаратное обеспечение

Алгоритмы, не основанные на сравнениях

Блочная сортировка (Корзинная сортировка, Bucket sort)
Лексикографическая или поразрядная сортировка (Radix sort)
Сортировка подсчётом (Counting sort)

Остальные алгоритмы сортировки

См. также

Ёмкостная сложность алгоритма
Сортирующие сети (сравнение)
Сравнивание
Трансформация Шварца
Параллельная сортировка

Литература

Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. - 2-е изд. - М.: «Вильямс» , 2007. - С. 824. - ISBN 0-201-89685-0
Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. - 2-е изд. - М.: «Вильямс» , 2006. - С. 1296. - ISBN 0-07-013151-1
Роберт Седжвик Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching. - СПб.: ДиаСофтЮП, 2003. - С. 672. - ISBN 5-93772-081-4

Ссылки

Анимированное сравнение алгоритмов сортировки (англ.)

Wikimedia Foundation . 2010 .

Смотреть что такое "Методы сортировки" в других словарях:

класс сортировки - Классификация контролируемого изделия в одном диапазоне или в нескольких диапазонах требуемых характеристик, например твердости, состава материала или размеров. [Система неразрушающего контроля. Виды (методы) и технология неразрушающего контроля … Справочник технического переводчика

ГОСТ Р ИСО 14644-3-2007: Чистые помещения и связанные с ними контролируемые среды. Часть 3. Методы испытаний - Терминология ГОСТ Р ИСО 14644 3 2007: Чистые помещения и связанные с ними контролируемые среды. Часть 3. Методы испытаний оригинал документа: 3.2.11 U дескриптор (U descriptor): Полученное или заданное количество частиц, включая ультрамелкие… …

ГОСТ Р ИСО 2859-5-2009: Статистические методы. Процедуры выборочного контроля по альтернативному признаку. Часть 5. Система последовательных планов на основе AQL для контроля последовательных партий - Терминология ГОСТ Р ИСО 2859 5 2009: Статистические методы. Процедуры выборочного контроля по альтернативному признаку. Часть 5. Система последовательных планов на основе AQL для контроля последовательных партий оригинал документа: 3.36… … Словарь-справочник терминов нормативно-технической документации

У этого термина существуют и другие значения, см. Триаж (значения). Триаж во Франции, Первая мировая война. Медицинская сортир … Википедия

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

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

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

В данной статье постараемся это выяснить. Для обеспечения наилучших результатов все представленные алгоритмы будут сортировать целочисленный массив из 200 элементов. Компьютер, на котором будет проводится тестирование имеет следующие характеристики: процессор AMD A6-3400M 4x1.4 GHz, оперативная память 8 GB, операционная система Windows 10 x64 build 10586.36.

Для проведения исследования были выбраны следующие алгоритмы сортировки:

Selection sort (сортировка выбором) – суть алгоритма заключается в проходе по массиву от начала до конца в поиске минимального элемента массива и перемещении его в начало. Сложность такого алгоритма O(n2).

Bubble sort (сортировка пузырьком) – данный алгоритм меняет местами два соседних элемента, если первый элемент массива больше второго. Так происходит до тех пор, пока алгоритм не обменяет местами все неотсортированные элементы. Сложность данного алгоритма сортировки равна O(n^2).

Insertion sort (сортировка вставками) – алгоритм сортирует массив по мере прохождения по его элементам. На каждой итерации берется элемент и сравнивается с каждым элементом в уже отсортированной части массива, таким образом находя «свое место», после чего элемент вставляется на свою позицию. Так происходит до тех пор, пока алгоритм не пройдет по всему массиву. На выходе получим отсортированный массив. Сложность данного алгоритма равна O(n^2).

Quick sort (быстрая сортировка) – суть алгоритма заключается в разделении массива на два под-массива, средней линией считается элемент, который находится в самом центре массива. В ходе работы алгоритма элементы, меньшие чем средний будут перемещены в лево, а большие в право. Такое же действие будет происходить рекурсивно и с под-массива, они будут разделяться на еще два под-массива до тех пор, пока не будет чего разделать (останется один элемент). На выходе получим отсортированный массив. Сложность алгоритма зависит от входных данных и в лучшем случае будет равняться O(n×2log2n). В худшем случае O(n^2). Существует также среднее значение, это O(n×log2n).

Comb sort (сортировка расческой) – идея работы алгоритма крайне похожа на сортировку обменом, но главным отличием является то, что сравниваются не два соседних элемента, а элементы на промежутке, к примеру, в пять элементов. Это обеспечивает от избавления мелких значений в конце, что способствует ускорению сортировки в крупных массивах. Первая итерация совершается с шагом, рассчитанным по формуле (размер массива)/(фактор уменьшения), где фактор уменьшения равен приблизительно 1,247330950103979, или округлено до 1,3. Вторая и последующие итерации будут проходить с шагом (текущий шаг)/(фактор уменьшения) и будут происходить до тех пор, пока шаг не будет равен единице. Практически в любом случае сложность алгоритма равняется O(n×log2n).

Для проведения тестирования будет произведено по 5 запусков каждого алгоритма и выбрано наилучшее время. Наилучшее время и используемая при этом память будут занесены в таблицу. Также будет проведено тестирование скорости сортировки массива размером в 10, 50, 200 и 1000 элементов чтобы определить для каких задач предназначен конкретный алгоритм.

Полностью неотсортированный массив:

Частично отсортированный массив (половина элементов упорядочена):

Результаты, предоставленые в графиках:

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

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

Откуда взялось такое необычное название?

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

Описание алгоритма

Сортировка пузырьком выполняется следующим образом:

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

Еще короче алгоритм будущей программы можно записать так:

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

Псевдокод на основе описанного алгоритма

Самая простая реализация выполняется так:

Процедура Sortirovka_Puzirkom ;

Начало

цикл для j от nachalnii_index до konechii_index ;

цикл для i от nachalnii_index до konechii_index-1 ;

если massiv[i]>massiv

(меняем значения местами);

Конец

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

Потребовалась реализация получше. Например, учитывающая обмен значений в массиве местами:

Процедура Sortirovka_Puzirkom ;

Начало

sortirovka = истина;

цикл пока sortirovka = истина;

sortirovka = ложь;

цикл для i от nachalnii_index до konechii_index-1 ;

если massiv[i]>massiv (первый элемент больше второго), то:

(меняем элементы местами);

sortirovka = истина; (обозначили, что обмен был произведен).

Конец.

Недостатки метода

Основной минус - продолжительность процесса. Сколько же времени выполняется пузырьком?

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

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

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

Достоинства

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

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

Наглядный принцип сортировки

Изначальный вид массива 8 22 4 74 44 37 1 7

Шаг 1 8 22 4 74 44 37 1 7

8 22 4 74 44 1 37 7

8 22 4 74 1 44 37 7

8 22 4 1 74 44 37 7

8 22 1 4 74 44 37 7

8 1 22 4 74 44 37 7

1 8 22 4 74 44 37 7

Шаг 2 1 8 22 4 74 44 7 37

1 8 22 4 74 7 44 37

1 8 22 4 7 74 44 37

1 8 4 22 7 74 44 37

1 4 8 22 7 74 44 37

Шаг 3 1 4 8 22 7 74 37 44

1 4 8 22 7 37 74 44

1 4 8 7 22 37 74 44

1 4 7 8 22 37 74 44

Шаг 4 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Шаг 5 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Шаг 6 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Шаг 7 1 4 7 8 22 37 44 74

Пример сортировки пузырьком на языке Pascal

Пример:

const kol_mas=10;

var massiv:array of integer;

a, b, k: integer;

writeln ("input", kol_mas, "elements of array");

for a:=1 to kol_mas do readln(massiv[a]);

for a:=1 to kol_mas-1 do begin

for b:=a+1 to kol_mas do begin

if massiv[a]>massiv[b] then begin

k:=massiv[a]; massiv[a]:=massiv[b]; massiv[b]:=k;

end;

writeln ("after sort");

for a:=1 to kol_mas do writeln(massiv[a]);

Пример сортировки пузырьком на языке С (Си)

#include

int main(int argc, char* argv)

int massiv = {36, 697, 73, 82, 68, 12, 183, 88},i, ff;

for (; ;){

ff = 0;

for (i = 7; i>0; i--){

if (massiv[i] < massiv) {

swap (massiv[i],massiv);

if (ff == 0) break;

getch(); // задержка экрана

Полностью неотсортированный массив:

Частично отсортированный массив (половина элементов упорядочена):

Результаты, предоставленые в графиках: