Сортировка пузырьком по возрастанию c. Сортировка пузырьком (Pascal). Откуда взялось такое необычное название

• into – метод вставки элементов в массив;
• printer – выводит содержимое массива построчно;

toSwap – переставляет местами элементы в случае необходимости. Для этого используется временная переменная dummy , в которую записывается значение первого числа, а на место первого записывается значение из второго числа. После этого содержимое из временной переменной записывается во второе число. Это стандартный прием перестановки местами двух элементов;

и, наконец, главный метод:

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

  public void bubbleSorter () { //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ for (int out = elems - 1 ; out >= 1 ; out-- ) { //Внешний цикл for (int in = 0 ; in out; in++ ) { //Внутренний цикл if (a[ in] > a[ in + 1 ] ) //Если порядок элементов нарушен toSwap (in, in + 1 ) ; //вызвать метод, меняющий местами } } }

Заключение

На скорость алгоритма влияет не только количество проходов, но и количество перестановок, которые потребуется совершить. Для случайных данных количество перестановок в среднем составляет (N^2) / 4, то есть примерно в половину меньше, чем количество проходов. Однако, в худшем случае количество перестановок также может составить N^2 / 2 – это в том случае, если данные изначально отсортированы в обратном порядке. Не смотря на то, что это достаточно медленный алгоритм сортировки, знать и понимать как он работает довольно важно, к тому же, как было сказано ранее, он является основой для более сложных алгоритмов. Jgd!

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

Решение

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

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

Алгоритм и особенности этой сортировки таковы:

1. При первом проходе по массиву элементы попарно сравниваются между собой: первый со вторым, затем второй с третьим, следом третий с четвертым и т.д. Если предшествующий элемент оказывается больше последующего, то их меняют местами.
2. Не трудно догадаться, что постепенно самое большое число оказывается последним. Остальная часть массива остается не отсортированной, хотя некоторое перемещение элементов с меньшим значением в начало массива наблюдается.
3. При втором проходе незачем сравнивать последний элемент с предпоследним. Последний элемент уже стоит на своем месте. Значит, число сравнений будет на одно меньше.
4. На третьем проходе уже не надо сравнивать предпоследний и третий элемент с конца. Поэтому число сравнений будет на два меньше, чем при первом проходе.
5. В конце концов, при проходе по массиву, когда остаются только два элемента, которые надо сравнить, выполняется только одно сравнение.
6. После этого первый элемент не с чем сравнивать, и, следовательно, последний проход по массиву не нужен. Другими словами, количество проходов по массиву равно m-1, где m – это количество элементов массива.
7. Количество сравнений в каждом проходе равно m-i, где i – это номер прохода по массиву (первый, второй, третий и т.д.).
8. При обмене элементов массива обычно используется "буферная" (третья) переменная, куда временно помещается значение одного из элементов.

Программа на языке Паскаль:

const m = 10 ; var arr: array [ 1 .. m ] of integer ; i, j, k: integer ; begin randomize; write ("Исходный массив: " ) ; for i : = 1 to m do begin arr[ i] : = random(256 ) ; write (arr[ i] : 4 ) ; end ; writeln ; writeln ; for i : = 1 to m- 1 do for j : = 1 to m- i do if arr[ j] > arr[ j+ 1 ] then begin k : = arr[ j] ; arr[ j] : = arr[ j+ 1 ] ; arr[ j+ 1 ] : = k end ; write ("Отсортированный массив: " ) ; for i : = 1 to m do write (arr[ i] : 4 ) ; writeln ; readln end .

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

Алгоритм сортировки пузырьком сводится к повторению проходов по элементам сортируемого массива. Проход по элементам массива выполняет внутренний цикл. За каждый проход сравниваются два соседних элемента, и если порядок неверный элементы меняются местами. Внешний цикл будет работать до тех пор, пока массив не будет отсортирован. Таким образом внешний цикл контролирует количество срабатываний внутреннего цикла Когда при очередном проходе по элементам массива не будет совершено ни одной перестановки, то массив будет считаться отсортированным. Чтобы хорошо понять алгоритм, отсортируем методом пузырька массив, к примеру, из 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).

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

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

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

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

Отсортируем массив {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); } }

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