Алгоритмы и структуры данных для начинающих: сортировка. Методы сортировки в программировании: сортировка "пузырьком"

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

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

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

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

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

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

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

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

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

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

Процедура 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(); // задержка экрана

Существует три общих метода сортировки массивов:

Обмен
Выбор (выборка)
Вставка

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

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

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

Сортировка вставками

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

· эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;

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

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

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

Минусом -высокая сложность алгоритма: O(n ²)

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

Описание

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

Анализ Алгоритма

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

Реализация на java

public void addingSort() {

for (Node cur = first.next; cur != null ; cur = cur.next) {

Node n = cur.prev;

Object val = cur.value;

for (; n != null ; n = n.prev) {

if (((Comparable) n.value).compareTo(val) > 0) {

n.next.value = n.value;

} else {

if (n != null ) {

n.next.value = val;

} else {

first.value = val;

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

Начало d c a b

Проход 1 c d a b

Проход 2 a c d b

Проход 3 a b c d

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

Описание

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

Начало d c a bПроход 1 a c d bПроход 2 a b d cПроход 3 a b c d

Анализ

К сожалению, как и в пузырьковой сортировке, внешний цикл выполняется n - 1 раз, а внутренний - в среднем n /2 раз. Следовательно, сортировка посредством выбора требует 1/2(n 2 -n ) сравнений. Таким образом, это алгоритм порядка n 2 , из-за чего он считается слишком медленным для сортировки большого количества элементов. Несмотря на то, что количество сравнений в пузырьковой сортировке и сортировке посредством выбора одинаковое, в последней количество обменов в среднем случае намного меньше, чем в пузырьковой сортировке.

Реализация на java

public void SelectSort() {

for (Node a = first; a != last; a = a.next) {

Node min = last;

for (Node b = a; b != last; b = b.next) {

if (((Comparable) b.val).compareTo(min.val) < 0) {

a.val = min.val;

Сортировка Обменом

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

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

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

Начало d c a b

Проход 1 a d c b

Проход 2 a b d c

Проход 3 a b c d

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

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

(n 2 -n )/2

сравнений, где n - количество сортируемых элементов. Данная формула выведена на том основании, что внешний цикл выполняется n - 1 раз, а внутренний выполняется в среднем n /2 раз. Произведение этих величин и дает предыдущее выражение.

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

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

Похожая информация.

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

Алгоритмом сортировки называется алгоритм для упорядочения некоторого множества элементов. Обычно под алгоритмом сортировки подразумевают алгоритм упорядочивания множества элементов по возрастанию или убыванию.

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

В алгоритмах сортировки лишь часть данных используется в качестве ключа сортировки . Ключом сортировки называется атрибут (или несколько атрибутов), по значению которого определяется порядок элементов. Таким образом, при написании алгоритмов сортировок массивов следует учесть, что ключ полностью или частично совпадает с данными.

Алгоритм преобразования массива в пирамиду (построение пирамиды) . Пусть дан массив x,x,...,x[n] .

Шаг 1. Устанавливаем k=n/2 .

Шаг 2. Перебираем элементы массива в цикле справа налево для i=k,k-1,...,1 . Если неравенства x i > x 2i , x i > x 2i+1 не выполняются, то повторяем перестановки x i с наибольшим из потомков. Перестановки завершаются при выполнении неравенств x i > x 2i , x i > x 2i+1 .

Алгоритм сортировки пирамиды .

Рассмотрим массив размерности n , который представляет пирамиду x,x,...,x[n] .

Шаг 1. Переставляем элементы x и x[n] .

Шаг 2. Определяем n=n-1 . Это эквивалентно тому, что в массиве из дальнейшего рассмотрения исключается элемент x[n] .

Шаг 3. Рассматриваем массив x,x,...,x , который получается из исходного за счет исключения последнего элемента. Данный массив из-за перестановки элементов уже не является пирамидой. Но такой массив легко преобразовать в пирамиду . Это достигается повторением перестановки значения элемента из x с наибольшим из потомков. Такая перестановка продолжается до тех пор, пока элемент из x не окажется на месте элемента x[i] и при этом будут выполняться неравенства x[i] > x, x[i] > x . Тем самым определяется новое

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

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

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

Устойчивость (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), предполагая что сравнения делаются за постоянное… … Википедия