Пузырек сортировка. Реализация пузырьковой сортировки на Java

Теги: Сортировка пузырьком си, си пузырьковая сортировка, сортировка пузырьком двумерного массива

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

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

Отсортируем массив {1, 5, 2, 7, 6, 3}
Идём по массиву, проверяем первое число и второе, они идут в порядке возрастания. Далее идёт нарушение порядка, меняем местами эти элементы
1, 2, 5, 7, 6, 3
Продолжаем идти по массиву, 7 больше 5, а вот 6 меньше, так что обмениваем из местами
1, 2, 5, 6, 7, 3
3 нарушает порядок, меняем местами с 7
1, 2, 5, 6, 3, 7
Возвращаемся к началу массива и проделываем то же самое

1, 2, 5, 3, 6, 7
1, 2, 3, 5, 6, 7

Говорят, что это похоже на "всплытие" более "лёгких" элементов, как пузырьков, отчего алгоритм и получил такое название. void bubbleSort(int *a, size_t size) { size_t i, j; int tmp; for (i = 1; i < size; i++) { for (j = 1; j < size; j++) { if (a[j] > a) { tmp = a[j]; a[j] = a; a = tmp; } } } }

Этот алгоритм всегда будет делать (n-1) 2 шагов, независимо от входных данных. Даже если массив отсортирован, всё равно он будет пройден (n-1) 2 раз. Более того, будут в очередной раз проверены уже отсортированные данные.

Пусть нужно отсортировать массив 1, 2, 4, 3

1 2 4 3
1 2 4 3
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4

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

Void bubbleSort2(int *a, size_t size) { size_t i, j; int tmp; for (i = 1; i < size; i++) { for (j = i; j > 0; j--) { if (a[j] < a) { tmp = a[j]; a[j] = a; a = tmp; } } } }

Ещё одна реализация

Void bubbleSort2b(int *a, size_t size) { size_t i, j; int tmp; for (i = 1; i < size; i++) { for (j = 1; j <= size-i; j++) { if (a[j] < a) { tmp = a[j]; a[j] = a; a = tmp; } } } }

В данном случае будет уже вполовину меньше шагов, но всё равно остаётся проблема сортировки уже отсортированного массива: нужно сделать так, чтобы отсортированный массив функция просматривала один раз. Для этого введём переменную-флаг: он будет опущен (flag = 0), если массив отсортирован. Как только мы наткнёмся на нарушение порядка, то флаг будет поднят (flag = 1) и мы начнём сортировать массив как обычно.

Void bubbleSort3(int *a, size_t size) { size_t i; int tmp; char flag; do { flag = 0; for (i = 1; i < size; i++) { if (a[i] < a) { tmp = a[i]; a[i] = a; a = tmp; flag = 1; } } } while (flag); }

В этом случае сложность также порядка n 2 , но в случае отсортированного массива будет всего один проход.

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

Int intSort(const void *a, const void *b) { return *((int*)a) > *((int*)b); } void bubbleSort3g(void *a, size_t item, size_t size, int (*cmp)(const void*, const void*)) { size_t i; void *tmp = NULL; char flag; tmp = malloc(item); do { flag = 0; for (i = 1; i < size; i++) { if (cmp(((char*)a + i*item), ((char*)a + (i-1)*item))) { memcpy(tmp, ((char*)a + i*item), item); memcpy(((char*)a + i*item), ((char*)a + (i-1)*item), item); memcpy(((char*)a + (i-1)*item), tmp, item); flag = 1; } } } while (flag); free(tmp); }

Функция выглядит некрасиво – часто вычисляется адрес текущего и предыдущего элемента. Выделим отдельные переменные для этого.

Void bubbleSort3gi(void *a, size_t item, size_t size, int (*cmp)(const void*, const void*)) { size_t i; void *tmp = NULL; void *prev, *cur; char flag; tmp = malloc(item); do { flag = 0; i = 1; prev = (char*)a; cur = (char*)prev + item; while (i < size) { if (cmp(cur, prev)) { memcpy(tmp, prev, item); memcpy(prev, cur, item); memcpy(cur, tmp, item); flag = 1; } i++; prev = (char*)prev + item; cur = (char*)cur + item; } } while (flag); free(tmp); }

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

Void main() { int a = {1, 0, 9, 8, 7, 6, 2, 3, 4, 5}; int i; bubbleSort3gi(a, sizeof(int), 10, intSort); for (i = 0; i < 10; i++) { printf("%d ", a[i]); } _getch(); }

Сортировка многомерного массива

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

Void main() { int a = {1, 9, 2, 8, 3, 7, 4, 6, 5}; int i, j; bubbleSort3gi(a, sizeof(int), 9, intSort); for (i = 0; i < 3; i++) { for (j = 0; j < 3; j++) { printf("%d ", a[i][j]); } } } Сортировка динамически созданного двумерного массива может быть произведена двумя способами. Во-первых, можно по определённому алгоритму находить индекс i-го и j-го элемента по порядковому номеру k от 0 до n * m. #include #include #include #include void bubbleSort2d(int **a, size_t m, size_t n) { int tmp; size_t i, j, k, jp, ip; size_t size = m*n; char flag; do { flag = 0; for (k = 1; k < size; k++) { //Вычисляем индексы текущего элемента j = k / m; i = k - j*m; //Вычисляем индексы предыдущего элемента jp = (k-1) / m; ip = (k-1) - jp*m; if (a[i][j] > a) { tmp = a[i][j]; a[i][j] = a; a = tmp; flag = 1; } } } while(flag); } #define SIZE_X 3 #define SIZE_Y 4 void main() { int **a = NULL; int i, j; a = (int**) malloc(sizeof(int*) * SIZE_X); for (i = 0; i < SIZE_X; i++) { a[i] = (int*) malloc(sizeof(int) * SIZE_Y); for (j = 0; j < SIZE_Y; j++) { a[i][j] = rand(); printf("%8d ", a[i][j]); } printf("\n"); } printf("\nafter sort\n"); bubbleSort2d(a, SIZE_X, SIZE_Y); for (i = 0; i < SIZE_X; i++) { for (j = 0; j < SIZE_Y; j++) { printf("%8d ", a[i][j]); } printf("\n"); } for (i = 0; i < SIZE_X; i++) { free(a[i]); } free(a); _getch(); }

Во-вторых, можно сначала переместить массив в одномерный, отсортировать одномерный массив, после чего переместить его обратно в двумерный.

Void bubbleSort3gi2d(void **a, size_t item, size_t m, size_t n, int (*cmp)(const void*, const void*)) { size_t size = m*n, sub_size = n*item; size_t i, j, k; void *arr = malloc(size * item); char *p1d = (char*)arr; char *p2d = (char*)a; //Копируем двумерный массив типа void в одномерный for (i = 0; i < m; i++) { memcpy(p1d + i*sub_size, *((void**)(p2d + i*item)), sub_size); } bubbleSort3gi(arr, item, size, cmp); //Копируем одномерный массив обратно в двумерный for (i = 0; i < m; i++) { memcpy(*((void**)(p2d + i*item)), p1d + i*sub_size, sub_size); } }

Если вас смущает эта функция, то воспользуйтесь типизированной. Вызов, из предыдущего примера

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

image: пузырьки

Сегодня поговорим о простейших сортировках обменами .

Если кому интересно, скажу, что есть и другие классы – сортировки выбором , сортировки вставками , сортировки слиянием , сортировки распределением , гибридные сортировки и параллельные сортировки . Есть, кстати, ещё эзотерические сортировки . Это различные фейковые, принципиально нереализуемые, шуточные и прочие псевдо-алгоритмы, про которые я в хабе «IT-юмор» как-нибудь напишу пару статей.

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

Заранее предупрежу, что почти все приведённые способы весьма медленные и глубокого анализа их временной сложности не будет. Какие-то побыстрее, какие-то помедленнее, но, грубо говоря, можно сказать, что в среднем O (n 2 ). Также я не вижу резона загромождать статью реализациями на каких-либо языках программирования. Заинтересовавшиеся без малейшего труда смогут найти примеры кода на Розетте , в Википедии или где-нибудь ещё.

Но вернёмся к сортировкам обменами. Упорядочивание происходит в результате многократного последовательного перебора массива и сравнения пар элементов между собой. Если сравниваемые элементы не отсортированы друг относительно друга – то меняем их местами. Вопрос только в том, каким именно макаром массив обходить и по какому принципу выбирать пары для сравнения.

Начнём не с эталонной пузырьковой сортировки, а с алгоритма, который называется…

Глупая сортировка

«Так любой дурак сортировать умеет» - скажете Вы и будете абсолютно правы. Именно поэтому сортировку и прозвали «глупой». На этой лекции мы будем последовательно совершенствовать и видоизменять данный способ. Сейчас у него временная сложность O (n 3 ), произведя одну коррекцию, мы уже доведём до O (n 2 ), потом ускорим ещё немного, потом ещё, а в конце концов мы получим O (n log n ) – и это будет вовсе не «Быстрая сортировка»!

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

В этом случае перед нами не что иное как всем известная…

Пузырьковая сортировка

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

Шейкерная сортировка

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

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

Чётно-нечётная сортировка

В обычном «пузырьке» во время каждого прохода мы планомерно выдавливаем в конец массива текущий максимум. Если же передвигаться вприпрыжку по чётным и нечётным индексам, то сразу все более-менее крупные элементы массива одновременно за один пробег проталкиваются вправо на одну позицию. Так получается быстрее.

Разберём последнее покращення * для Сортування бульбашкою ** - Сортування гребінцем ***. Этот способ упорядочивает весьма шустро, O (n 2 ) – его наихудшая сложность. В среднем по времени имеем O (n log n ), а лучшая даже, не поверите, O (n ). То есть, весьма достойный конкурент всяким «быстрым сортировкам» и это, заметьте, без использования рекурсии. Впрочем, я обещал, что в крейсерские скорости мы сегодня углубляться не станем, засим умолкаю и перехожу непосредственно к алгоритму.

Во всём виноваты черепашки

image: виноватая черепашка

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

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

Опытным и теоретическим путём установлено оптимальное значение фактора уменьшения :

Когда был изобретён этот метод, на него на стыке 70-х и 80-х мало кто обратил внимание. Десятилетие спустя, когда программирование перестало быть уделом учёных и инженеров IBM, а уже лавинообразно набирало массовый характер, способ переоткрыли, исследовали и популяризировали в 1991 году Стивен Лейси и Ричард Бокс.

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

- Примечания

* покращення (укр. ) – улучшение
** Сортування бульбашкою (укр. ) – Сортировка пузырьком
*** Сортування гребінцем (укр. ) – Сортировка расчёской

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

Алгоритм сортировки пузырьком сводится к повторению проходов по элементам сортируемого массива. Проход по элементам массива выполняет внутренний цикл. За каждый проход сравниваются два соседних элемента, и если порядок неверный элементы меняются местами. Внешний цикл будет работать до тех пор, пока массив не будет отсортирован. Таким образом внешний цикл контролирует количество срабатываний внутреннего цикла Когда при очередном проходе по элементам массива не будет совершено ни одной перестановки, то массив будет считаться отсортированным. Чтобы хорошо понять алгоритм, отсортируем методом пузырька массив, к примеру, из 7 чисел (см. Таблица 1).
исходный массив: 3 3 7 1 2 5 0

Для того чтобы отсортировать массив хватило пяти запусков внутреннего цикла, for . Запустившись, цикл for срабатывал 6 раз, так как элементов в массиве 7, то итераций (повторений) цикла for должно быть на одно меньше. На каждой итерации сравниваются два соседних элемента массива. Если текущий элемент массива больше следующего, то меняем их местами. Таким образом, пока массив не будет отсортирован, будет запускаться внутренний цикл и выполняться операция сравнения. Обратите внимание на то, что за каждое полное выполнение цикла for как минимум один элемент массива находит своё место. В худшем случае, понадобится n-2 запуска внутреннего цикла, где n – количество элементов массива. Это говорит о том, что сортировка пузырьком крайне не эффективна для больших массивов.

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

// bu_sort.cpp: определяет точку входа для консольного приложения. #include "stdafx.h" #include #include #include using namespace std; void bubbleSort(int *, int); // прототип функции сортировки пузырьком int main(int argc, char* argv) { srand(time(NULL)); setlocale(LC_ALL, "rus"); cout << "Введите размер массива: "; int size_array; // длинна массива cin >> size_array; int *sorted_array = new int ; // одномерный динамический массив for (int counter = 0; counter < size_array; counter++) { sorted_array = rand() % 100; // заполняем массив случайными числами cout << setw(2) << sorted_array << " "; // вывод массива на экран } cout << "\n\n"; bubbleSort(sorted_array, size_array); // вызов функции сортировки пузырьком for (int counter = 0; counter < size_array; counter++) { cout << setw(2) << sorted_array << " "; // печать отсортированного массива } cout << "\n"; system("pause"); return 0; } void bubbleSort(int* arrayPtr, int length_array) // сортировка пузырьком { int temp = 0; // временная переменная для хранения элемента массива bool exit = false; // болевая переменная для выхода из цикла, если массив отсортирован while (!exit) // пока массив не отсортирован { exit = true; for (int int_counter = 0; int_counter < (length_array - 1); int_counter++) // внутренний цикл //сортировка пузырьком по возрастанию - знак > //сортировка пузырьком по убыванию - знак < if (arrayPtr > arrayPtr) // сравниваем два соседних элемента { // выполняем перестановку элементов массива temp = arrayPtr; arrayPtr = arrayPtr; arrayPtr = temp; exit = false; // на очередной итерации была произведена перестановка элементов } } }

Результат работы программы показан на рисунке 1.

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

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

Пример работы алгоритма

Возьмём массив с числами «5 1 4 2 8» и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.

Первый проход:

Второй проход:

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

Третий проход:

Теперь массив отсортирован и алгоритм может быть завершён.

Реализация алгоритма на различных языках программирования:

Синтаксис Intel

Mov bx, offset array mov cx, n for_i: dec cx xor dx, dx for_j: cmp dx, cx jae exit_for_j jbe no_swap mov ah, byte ptr bx mov byte ptr bx, al mov byte ptr bx, ah no_swap: inc dx jmp for_j exit_for_j: loop for_i

Синтаксис AT&T (GNU)

Text # void bubble_sort (unsigned *array, unsigned length); .globl bubble_sort .type bubble_sort, @function bubble_sort: mov 8(%esp), %ecx # unsigned length cmp $1, %ecx jbe exit mov 4(%esp), %eax # unsigned *array dec %ecx for_ecx: xor %edi, %edi for_edi: mov (%eax,%edi,4), %ebx cmp %ebx, 4(%eax,%edi,4) jae no_xchng mov 4(%eax,%edi,4), %edx mov %edx, (%eax,%edi,4) mov %ebx, 4(%eax,%edi,4) no_xchng: inc %edi cmp %edi, %ecx jne for_edi loop for_ecx exit: ret

C

#define SWAP(A, B) { int t = A; A = B; B = t; } void bubblesort(int *a, int n) { int i, j; for (i = n - 1; i > 0; i--) { for (j = 0; j < i; j++) { if (a[j] > a) SWAP(a[j], a); } } }

C++

С использованием Template

#include template< typename Iterator > void bubble_sort(Iterator First, Iterator Last) { while(First < --Last) for(Iterator i = First; i < Last; ++i) if (*(i + 1) < *i) std::iter_swap(i, i + 1); }

Без использования Template

Void bubble(int* a, int n) { for (int i = n - 1; i >= 0; i--) { for (int j = 0; j < i; j++) { if (a[j] > a) { int tmp = a[j]; a[j] = a; a = tmp; } } } }

C#

Void BubbleSort(int A) { for (int i = 0; i < A.Length; i++) { for (int j = i+1; j < A.Length; j++) { if (A[j] < A[i]) { var temp = A[i]; A[i] = A[j]; A[j] = temp; } } } }

Delphi

Сортировка одномерного динамического целочисленного массива:

Type TIntVec = array of Integer; ... procedure BubbleSort(var a: TIntVec); var i,p,n: Integer; b: boolean; begin n:= Length(a); if n < 2 then exit; repeat b:= false; Dec(n); if n > 0 then for i:= 0 to n-1 do if a[i] > a then begin p:= a[i]; a[i]:= a; a:= p; b:= true; end; until not b; end;

D

Void bubbleSort(alias op, T)(T inArray) { foreach (i, ref a; inArray) { foreach (ref b; inArray) { if (mixin(op)) { auto tmp = a; a = b; b = tmp; } } } }

Fortran

Do i=n-1,1,-1 do j=1,i if (a(j).gt.a(j+1)) then t=a(j) a(j)=a(j+1) a(j+1)=t endif enddo enddo

Java

Void bubblesort(int arr) { for (int i = 0; i < arr.length-1; i++){ for (int j = i+1; j < arr.length; j++){ if (arr[i] < arr[j]) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } } } }

Pascal

For i:=n-1 downto 1 do {n - размер массива M} for j:=1 to i do if M[j]>M then begin tmp:= M[j]; M[j]:= M; M:= tmp; end; write("вывод значений M: "); for i:=1 to n do write(M[i]:4); writeln;

Усовершенствованный алгоритм сортировки пузырьком:

P:=True; {есть перестановка?} K:=1; {Номер просмотра} While P Do Begin P:=false; For i:=1 To n-k Do If X[i] > X Then Begin A:=X[i]; X[i]:=X; X:=A; P:=true; End; k:=k+1; End;

Perl

For(@out){ for(0..$N-1){ if($out[$_]gt$out[$_+1]){ ($out[$_],$out[$_+1])=($out[$_+1],$out[$_]); } } }

Ruby

Arr = swap = true size = arr.length - 1 while swap swap = false for i in 0...size swap |= arr[i] > arr arr[i], arr = arr, arr[i] if arr[i] > arr end size -= 1 end puts arr.join(" ") # output => 1 3 3 5 8 10 11 12 17 20

Python

Def swap(arr, i, j): arr[i], arr[j] = arr[j], arr[i] def bubble_sort(arr): i = len(arr) while i > 1: for j in xrange(i - 1): if arr[j] > arr: swap(arr, j, j + 1) i -= 1

VBA

Sub Sort(Mus() As Long) Dim i As Long, tmp As Long, t As Boolean t = True Do While t t = False For i = 0 To UBound(Mus()) - 1 If Mus(i) > Mus(i + 1) Then tmp = Mus(i) Mus(i) = Mus(i + 1) Mus(i + 1) = tmp t = True End If Next Loop End Sub

PHP

$size = sizeof($arr)-1; for ($i = $size; $i>=0; $i--) { for ($j = 0; $j<=($i-1); $j++) if ($arr[$j]>$arr[$j+1]) { $k = $arr[$j]; $arr[$j] = $arr[$j+1]; $arr[$j+1] = $k; } }

JavaScript

Function sortBubble(data) { var tmp; for (var i = data.length - 1; i > 0; i--) { for (var j = 0; j < i; j++) { if (data[j] > data) { tmp = data[j]; data[j] = data; data = tmp; } } } return data; }

JavaFX

Function bubbleSort(seq:Number):Number{ var sort = seq; var elem:Number; for(n in reverse ){ for(i in ){ if(sort < sort[i]){ elem = sort[i]; sort[i] = sort; sort = elem; } } } return sort; }

Nemerle

Using System.Console; using Nemerle.Collections; def arr = array ; foreach (i in ) foreach (j in ) when (arr[j] > arr) (arr[j], arr) = (arr, arr[j]); WriteLine($"Sorted list is a $(arr.ToList())");

TurboBasic 1.1

CLS RANDOMIZE TIMER DEFINT X, Y, N, I, J, D N = 10 " 32 766 - 62.7 SEC DIM Y[N], Y1[N], Y2[N], Y3[N], Y4[N] "FRE(-1)=21440-21456 PRINT " ZAPOLNENIE MASSIVA ELEMENTAMI" FOR X = 1 TO N Y[X] = X PRINT Y[X]; NEXT X:PRINT PRINT " PEREMESHIVANIJE ELEMENTOV MASSIVA" PRINT " SLUCHAINYE CHISLA" FOR X = 1 TO N YD=Y[X] XS=INT(RND*N)+1 PRINT XS; Y[X]=Y Y=YD NEXT X:PRINT PRINT " PEREMESHANNYJ MASSIV" FOR X=1 TO N PRINT Y[X]; NEXT X:PRINT "ALGORITM "SORTIROVKA PROSTYM OBMENOM" O(N^2) MTIMER FOR J=1 TO N-1 STEP 1 F=0 FOR I=1 TO N-J STEP 1 "IF Y[I] > Y THEN D=Y[I]:Y[I]=Y:Y=D:F=1 IF Y[I] > Y THEN SWAP Y[I],Y:F=1 LOCATE 8,1 REM PRINT " ANYMACIJA SORTIROVKI" REM FOR X1=1 TO N REM ANIMATION BLOCK PRINT Y; REM NEXT X1:PRINT REM DELAY .5 REM NEXT I IF F=0 THEN EXIT FOR NEXT J T1=MTIMER PRINT " OTSORTIROVANNYJ MASSIV" FOR X=1 TO N PRINT Y[X]; NEXT X:PRINT PRINT "ELAPSED TIME=";T1

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

При написании статьи были использованы открытые источники сети интернет: