Алгоритм сортировки пузырьком заключается в последовательных обходах массива с перестановкой пар соседних элементов ( если нужно ) таким образом, что на каждом обходе максимальный элемент "всплывает" к концу массива — как пузырек в воде. Требуется n-1 обход, чтобы отсортировать массив ( n — число элементов массива ). Этот алгоритм используется в основном для обучения.
В начале работы алгоритма (на шаге "Ввод: массив А") можно задать массив, который будет отсортирован. Массив может содержать от 2-х до 12-ти элементов, каждый из которых может принимать значения от 0 до 20. "Всплывающий" на каждом шаге элемент, а также "всплывшие" на предыдущих шагах, закрашиваются коричневым цветом. Пара соседних элементов элементов массива, сравниваемых друг с другом на шаге A[j]>A[j+1], мерцают. Визуализация данных и их изменений позволяют легче понять суть работы алгоритма.
Можно также запустить оптимизированную версию алгоритма — Пузырьковая сортировка 2.
Подробнее об алгоритме можно узнать например в статье Википедии.
Сортировка пузырьком (Bubble sort) – простой алгоритм сортировки обменами, который считается учебным и практически не применяется вне учебной литературы.
Пусть задан массив из n элементов. Для сортировки его элементов метод «пузырька» будет иметь следующую последовательность шагов.
1. Шаг инициализации. Для каждого прохода 
позиция последней перестановки элементов LastExchange принимается равной номеру последнего элемента массива n-1.
2. Шаг итерации. Для всех элементов с нулевой позиций до позиции последнего обмена производится сравнение со следующим элементом. Если текущий элемент оказывается больше следующего, то они переставляются, и позиция последнего обмена устанавливается равной текущему элементу.
3. Шаг выхода. Первый и второй шаги повторяются до тех пор, пока позиция последнего обмена не станет равной нулю.
Пусть дан следующий массив:
Оченка вычислительной сложности алгоритма показывает, что в наилучшем случае без учета LastExchange будет 
, т.е. 
.
Однако, на каждом (n-1) проходе сравниваемые элементы в наихудшем случае (когда массив отсортирован по убыванию) придется переставлять 
, т.е. число перестановок будет иметь порядок сложности . В наилучшем случае, когда массив отсортирован по возрастанию и используется позиция последней перестановки LastExchange, число сравнений будет (n-1), а перестановок не будет. Анализ общего случая затруднен из-за случайности обмена. Однако, из-за большого количества перестановок данный алгоритм является самый медленный из всех существующих.
Блок-схема алгоритма сортировки методом «пузырька» имеет следующий вид:
Реализовать данный алгоритм можно следующим образом:
template
void BubbleSort(T *A, const int n)
int i=n-1, LastExchange=n-1;
while (i > 0)
for (int j = 0; j A[j+1])
Быстрая сортировка
Рассмотрим следующий вид сортировки, которая называется быстрая сортировка.
Пример дан массив, случайным образом в нем выбираем элемент. Допустим это тройка.
После этого все, что меньше тройки мы двигаем влево, а больше вправо. Получим следующий массив.
И отдельно теперь отсортируем все что левее тройки и правее тройки
Получим отсортированный массив.
Реализация алгоритма на Паскале будет иметь следующий вид:
a:array [0..n] of integer;
procedure swap(var a,b:integer);
while i x) do dec(j);
if (i I then qsort(i,r);
Размер массива 100 элементов
Упорядоченный в обратном порядке
Заданный злучайным оброзом
Размер массива 500 элементов
Упорядоченный в обратном порядке
Заданный злучайным оброзом
Размер массива 1000 элементов
Упорядоченный в обратном порядке
Заданный злучайным оброзом
По полученным данным можно сказать, что наиболее целесообразно использовать быструю сортировку массива, она обеспечивает выполнения сортировки за минимальное время особенно это сказывается при больших массивах.
Методика работы с программой.
При запуске программы появится информация об том, что это за программа и для каких целей она необходима. После этого надо выбрать нажать клавишу Enter и появится информация о выборе размера массива. Если хотите выбрать массив состоящий из 100 элементов, то необходимо нажать клавишу Enter. После этого надо будет выбрать способ первоначальной упорядоченности массива: если хотите выбрать отсортированный в прямом порядке нажмите 1 Enter. Если хотите выбрать отсортированный в обратном порядке нажмите клавишу 2 и Enter. Отсортированный наполовину 3 и клавишу Enter. И наконец массив заданный случайным образом надо выбрать 4.
После этого компьютер попросит нажать Ввод. Если сортировка будет проходить длительное время то вы увидите сообщения о том, что вам надо подождать.
Дальше появится результаты работы программы, которые отображены будут в виде трех гистограмм. Первая гистограмма это количество перестановок для трех различных сортировок массива. Вторая гистограмма это количество сравнений для трех различных сортировок массива. Третья это время каждой из сортировок.