Пухирцеве сортування сі. Пухирцеве сортування (Bubble-sort). А ось відеоурок

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

Рішення

Існує безліч методів сортування. Одні є ефективнішими, інші – простіше розуміння. Досить простим для розуміння є сортування методом бульбашки, який також називають методом простого обміну. У чому він полягає, і чому в нього така дивна назва: "метод бульбашки"?

Як відомо повітря легше за воду, тому бульбашки повітря спливають. Це просто аналогія. У сортуванні методом бульбашки по зростанню легші (з меншим значенням) елементи поступово "спливають" на початок масиву, а важчі один за одним опускаються на дно (наприкінці масиву).

Алгоритм та особливості цього сортування такі:

При першому проході масивом елементи попарно порівнюються між собою: перший з другим, потім другий з третім, слідом третій з четвертим і т.д. Якщо попередній елемент виявляється більше наступного, їх змінюють місцями.
Не важко здогадатися, що поступово найбільше виявляється останнім. Решта масиву залишається не відсортованою, хоча деяке переміщення елементів з меншим значенням початку масиву спостерігається.
При другому проході нема чого порівнювати останній елемент із передостаннім. Останній елемент стоїть на своєму місці. Значить, число порівнянь буде менше.
На третьому проході не треба порівнювати передостанній і третій елемент із кінця. Тому число порівнянь буде на два менше, ніж за першого проходу.
Зрештою, при проході масивом, коли залишаються тільки два елементи, які треба порівняти, виконується тільки одне порівняння.
Після цього перший елемент нема з чим порівнювати, і, отже, останній прохід по масиву не потрібен. Іншими словами, кількість проходів масивом дорівнює m-1, де m - це кількість елементів масиву.
Кількість порівнянь у кожному проході дорівнює m-i, де i – це номер проходу масивом (перший, другий, третій тощо.).
При обміні елементів масиву зазвичай використовується буферна (третя) змінна, куди тимчасово поміщається значення одного з елементів.

Програма мовою Паскаль:

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.

Деталі Категорія: Сортування та пошук

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

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

Найгірший час
Найкращий час
Середній час
Витрати пам'яті

Приклад роботи алгоритму

Візьмемо масив з числами «5 1 4 2 8» і відсортуємо значення за зростанням, використовуючи сортування бульбашкою. Виділено ті елементи, які порівнюються на цьому етапі.

Перший прохід:

(5 1 4 2 8) (1 5 4 2 8), Тут алгоритм порівнює два перші елементи та змінює їх місцями. (1 5 4 2 8) (1 4 5 2 8), Змінює місцями, оскільки (1 4 5 2 8) (1 4 2 5 8), змінює місцями, оскільки (1 4 2 5 8 ) (1 4 2 5 8 ), Тепер, зважаючи на те, що елементи стоять на своїх місцях (), алгоритм не змінює їх місцями.

Другий прохід:

(1 4 2 5 8) (1 4 2 5 8) (1 4 2 5 8) (1 2 4 5 8), Змінює місцями, оскільки (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8 ) (1 2 4 5 8 )

Тепер масив повністю відсортований, але алгоритм не знає, чи це так. Тому йому необхідно зробити повний прохід та визначити, що перестановок елементів не було.

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

(1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8 ) (1 2 4 5 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_s 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 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 | 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): якщо 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 tt = 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; використовуючи Nemerle.Collections; def arr = array; foreach (i in ) foreach (j in ) when (arr[j] > arr) (arr[j], arr) = (arr, arr[j]); WriteLine($"Sorted list є $(arr.ToList())");

TurboBasic 1.1

CLS RANDOMIZE TIMER DEFINT X, Y, N, I, J, DN = 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 NY [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 NJ STEP 1 "IF Y [I]> 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. NEXT X:PRINT PRINT "ELAPSED TIME=";T1

Як зазначалося, алгоритм рідко використовується практично, оскільки має низьку продуктивність. У кращому випадку сортування бульбашкою вимагатиме O(n) часу, а в середньому та гіршому – O(n2).

При написанні статті було використано відкриті джерела мережі інтернет:

Розташуємо масив зверху донизу, від нульового елемента - до останнього.

Ідея методу: крок сортування полягає у проході знизу вгору масивом. Дорогою проглядаються пари сусідніх елементів. Якщо елементи певної пари перебувають у неправильному порядку, змінюємо їх місцями.

Після нульового проходу по масиву "вгорі" виявляється "найлегший" елемент - звідси аналогія з бульбашкою. Наступний прохід робиться до другого зверху елемента, таким чином другий за величиною елемент піднімається на правильну позицію.

Робимо проходи по нижній частині масиву, що все зменшується, доти, поки в ній не залишиться тільки один елемент. У цьому сортування закінчується, оскільки послідовність упорядкована за зростанням.

Template void bubbleSort(T a, long size) (long i, j; T x; for(i=0; i< size; i++) { // i - номер проходу for(j = size-1; j > i; j--) ( //Внутрішній цикл проходу if (a > a[j]) ( x=a; a=a[j]; a[j]=x; ) ) ) )

Середня кількість порівнянь та обмінів мають квадратичний порядок зростання: Theta(n 2), звідси можна зробити висновок, що алгоритм бульбашки дуже повільний і малоефективний.
Тим не менш, у нього є величезний плюс: він простий і його можна по-різному покращувати. Чим ми зараз і займемося.

По-перше, розглянемо ситуацію, коли на якомусь із проходів не відбулося жодного обміну. Що це означає?

Це означає, що всі пари розташовані в правильному порядку, тому масив вже відсортований. І продовжувати процес немає сенсу (особливо, якщо масив був відсортований від початку!).

Отже, перше покращення алгоритму полягає у запам'ятовуванні, чи здійснювався на даному проході якийсь обмін. Якщо ні – алгоритм закінчує роботу.

Процес поліпшення можна продовжити, якщо запам'ятовувати як сам факт обміну, а й індекс останнього обміну k. Дійсно: всі пари сусідніх елементів з індексами, меншими за k, вже розташовані в потрібному порядку. Подальші проходи можна закінчувати на індексі k, замість рухатися до встановленої заздалегідь верхньої межі i.

Якісно інше покращення алгоритму можна отримати з наступного спостереження. Хоча легка бульбашка знизу підніметься нагору за один прохід, важкі бульбашки опускаються з мінімальною швидкістю: один крок за ітерацію. Так що масив 2 3 4 5 6 1 буде відсортований за 1 прохід, а сортування послідовності 6 1 2 3 4 5 вимагатиме 5 проходів.

Щоб уникнути подібного ефекту, можна змінювати напрямок наступних один за одним проходів. Алгоритм, що вийшов, іноді називають " шейкер-сортуванням".

Template void shakerSort(T a, long size) (long j, k = size-1; long lb = 1, ub = size-1; // межі невідсортованої частини масиву T x; do ( // прохід знизу нагору for(j=ub; j>0; j--) ( if (a > a[j]) ( x=a; a=a[j]; a[j]=x; k=j; ) ) lb = k+1; // прохід зверху донизу for (j=1; j<=ub; j++) { if (a >a [j]) (x = a; a = a [j]; a [j] = x; k = j;)) ub = k-1; ) while (lb< ub); }

Наскільки ці зміни вплинули на ефективність методу? Середня кількість порівнянь, хоч і зменшилася, але залишається O(n 2), тоді як кількість обмінів не змінилося взагалі. Середня (воно ж найгірше) кількість операцій залишається квадратичною.

Додаткова пам'ять, мабуть, не потрібна. Поведінка вдосконаленого (але не початкового) методу досить природна, майже відсортований масив буде відсортований набагато швидше за випадковий. Сортування бульбашкою стійка, проте шейкер-сортировка втрачає цю якість.

Насправді метод бульбашки, навіть із поліпшеннями, працює, на жаль, занадто повільно. А тому – майже не застосовується.

Теги: Сортування бульбашкою си, си бульбашка сортування, сортування бульбашкою двовимірного масиву

Сортування бульбашкою

І дія алгоритму дуже проста. Ідемо по масиву чисел і перевіряємо порядок (наступне число має бути більше і дорівнює попередньому), як тільки натрапили на порушення порядку, відразу обмінюємо місцями елементи, доходимо до кінця масиву, після чого починаємо спочатку.

Відсортуємо масив (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;< 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;< 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;< 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); } }

Якщо вас непокоїть ця функція, то скористайтеся типізованою. Виклик, з попереднього прикладу

Не тільки не вважається самим швидким методомБільш того, вона замикає перелік найповільніших способів упорядкування. Однак і вона має свої плюси. Так, сортування методом бульбашки - що є логічне і природне вирішення проблеми, якщо необхідно розставити елементи в певному порядку. Звичайна людина вручну, наприклад, скористається саме нею - просто з інтуїції.

Звідки взялася така незвичайна назва?

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

Опис алгоритму

Сортування бульбашкою виконується так:

перший прохід: елементи масиву чисел беруться по два і парами порівнюються. Якщо в якійсь двійці елементів перше значення виявляється більшим за друге, програма здійснює їх обмін місцями;
отже, потрапляє до кінця масиву. Тоді як всі інші елементи залишаються, як і були, хаотично і вимагають ще сортування;
тому й необхідний другий прохід: проводиться він за аналогією з попереднім (вже описаним) і має число порівнянь – мінус один;
у проходу номер три порівнянь на одиницю менше, ніж у другого, та на двійку, ніж у першого. І так далі;
підсумуємо, кожен прохід має (всього значень у масиві, конкретне число) мінус (номер проходу) порівнянь.

Ще коротше алгоритм майбутньої програми можна записати так:

масив чисел перевіряється до того часу, доки знайдено якісь два числа, причому друге має бути більше першого;
неправильно розташовані один до одного елементи масиву програма змінює місцями.

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

Найпростіша реалізація виконується так:

Процедура Sortirovka_Puzirkom;

початок

цикл для jвід nachalnii_indexдо konechii_index;

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

якщо massiv[i]>massiv

(Змінюємо значення місцями);

Кінець

Звичайно, тут простота лише посилює ситуацію: чим простіше алгоритм, тим більше у ньому проявляються всі недоліки. Витрата часу надто велика навіть для невеликого масиву (тут входить у справу відносність: для обивателя кількість часу може здаватися маленьким, але у справі програміста кожна секунда або навіть мілісекунду на рахунку).

Потрібна була реалізація краще. Наприклад, що враховує обмін значень у масиві місцями:

Процедура Sortirovka_Puzirkom;

початок

salovka = істина;

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

salovka = брехня;

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

якщо massiv[i]>massiv(перший елемент більший за другий), то:

(Міняємо елементи місцями);

salovka = істина; (Позначили, що обмін був зроблений).

Кінець.

Недоліки методу

Основний мінус – тривалість процесу. Скільки часу виконується бульбашкою?

Час виконання розраховується із квадрата кількості чисел у масиві - кінцевий результат йому пропорційний.

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

Крім того, ефективний метод сортування простими обмінами, Як його ще називають, тільки для масивів невеликого розміру. Великі обсяги даних з його допомогою обробити не вийде: результатом стануть помилки або збій роботи програми.

Переваги

Сортування бульбашкою дуже проста для розуміння. У навчальних програмах технічних ВНЗ щодо впорядкування елементів масиву її проходять насамперед. Метод легко реалізується як мовою програмування 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 до kol_mas до readln(massiv[a]);

for a:=1 to kol_mas-1 do begin

для b:=a+1 до 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");

для:=1 до kol_mas до 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(); // Затримка екрану