БУЛЬБАШКОВЕ СОРТУВАННЯ

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

mergesort java

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

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

Bubble short в основному використовується там, де -

складність не має значення
простий і короткий код є кращим

Алгоритм

У наведеному нижче алгоритмі припустимо обр є масивом п елементів. Припускається своп функція в алгоритмі поміняє місцями значення заданих елементів масиву.

 begin BubbleSort(arr) for all array elements if arr[i] &gt; arr[i+1] swap(arr[i], arr[i+1]) end if end for return arr end BubbleSort

Робота алгоритму бульбашкового сортування

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

Щоб зрозуміти роботу алгоритму бульбашкового сортування, візьмемо несортований масив. Ми беремо короткий і точний масив, оскільки знаємо складність бульбашкового сортування O(n²).

Нехай елементи масиву -

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

Сортування почнеться з перших двох елементів. Давайте порівняємо їх, щоб перевірити, що більше.

Тут 32 більше за 13 (32 > 13), тому воно вже відсортовано. Тепер порівняйте 32 з 26.

Тут 26 менше, ніж 36. Отже, потрібна заміна. Після заміни новий масив буде виглядати так -

Тепер порівняйте 32 і 35.

Тут 35 більше, ніж 32. Отже, заміна не потрібна, оскільки вони вже відсортовані.

Тепер порівняння буде між 35 і 10.

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

Тепер переходимо до другої ітерації.

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

Той самий процес буде виконано для другої ітерації.

Тут 10 менше, ніж 32. Отже, потрібна заміна. Після заміни масив буде -

Тепер переходимо до третьої ітерації.

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

Той самий процес буде виконано для третьої ітерації.

Тут 10 менше, ніж 26. Отже, потрібна заміна. Після заміни масив буде -

Тепер переходимо до четвертої ітерації.

Четвертий прохід

Аналогічно, після четвертої ітерації, масив буде -

як переробити в фотошопі

Отже, заміна не потрібна, тому масив повністю відсортовано.

Складність бульбашкового сортування

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

1. Складність часу

Справа	Складність часу
Кращий випадок	O(n)
Середній випадок	O(n²)
Найгірший випадок	O(n²)

O(n).

O(n²).

2. Просторова складність

Космічна складність	O(1)
Стабільний	ТАК

Просторова складність бульбашкового сортування дорівнює O(1). Це тому, що в бульбашковому сортуванні потрібна додаткова змінна для заміни.
Просторова складність оптимізованого бульбашкового сортування становить O(2). Це тому, що для оптимізованого бульбашкового сортування потрібні дві додаткові змінні.

Тепер давайте обговоримо оптимізований алгоритм бульбашкового сортування.

Оптимізований алгоритм бульбашкового сортування

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

Щоб її вирішити, ми можемо використати додаткову змінну поміняні місцями. Він налаштований на правда якщо потрібна заміна; інакше встановлено значення помилковий.

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

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

Алгоритм оптимізованого бульбашкового сортування

 bubbleSort(array) n = length(array) repeat swapped = false for i = 1 to n - 1 if array[i - 1] &gt; array[i], then swap(array[i - 1], array[i]) swapped = true end if end for n = n - 1 until not swapped end bubbleSort

Реалізація бульбашкового сортування

Тепер давайте подивимося на програми Bubble sort на різних мовах програмування.

sql вибрати як

програма: Напишіть програму для реалізації бульбашкового сортування мовою C.

 #include void print(int a[], int n) //function to print array elements { int i; for(i = 0; i <n; i++) { printf('%d ',a[i]); } void bubble(int a[], int n) function to implement bubble sort i, j, temp; for(i="0;" i < n; for(j="i+1;" j j++) if(a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" main () j,temp; a[5]="{" 10, 35, 32, 13, 26}; n="sizeof(a)/sizeof(a[0]);" printf('before sorting array elements are - 
'); print(a, n); bubble(a, printf('
after pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-13.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in C++ language.</p> <pre> #include using namespace std; void print(int a[], int n) //function to print array elements { int i; for(i = 0; i <n; i++) { cout< <a[i]<<' '; } void bubble(int a[], int n) function to implement bubble sort i, j, temp; for(i="0;" i < n; for(j="i+1;" j j++) if(a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" main() j,temp; a[5]="{45," 1, 32, 13, 26}; n="sizeof(a)/sizeof(a[0]);" cout<<'before sorting array elements are - 
'; print(a, n); bubble(a, cout<<'
after return 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-14.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in C# language.</p> <pre> using System; public class Bubble { static void print (int[]a) //function to print array elements { int n = a.Length; int i; for (i = 0; i <n; 26 i++) { console.write (' ' + a[i]); } static void bubble (int[]a) function to implement sort int n="a.Length;" i, j, temp; for (i="0;" i < n; (j="i" 1; j j++) if (a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" public main () int[] a="{" 45, 1, 32, 13, }; ('
 before sorting array elements are - 
'); print (a); console.writeline (); after pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-15.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in Java.</p> <pre> public class Bubble { static void print (int a[]) //function to print array elements { int n = a.length; int i; for (i = 0; i <n; i++) { system.out.print(a[i] + ' '); } static void bubblesort (int a[]) function to implement bubble sort int n="a.length;" i, j, temp; for (i="0;" i < n; (j="i" 1; j j++) if (a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" public main(string[] args) a[]="{35," 10, 31, 11, 26}; b1="new" bubble(); system.out.println('before sorting array elements are - b1.print(a); b1.bubblesort(a); system.out.println(); system.out.println('after pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-16.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in JavaScript.</p> <pre> var a = [35, 10, 31, 11, 26]; function print() //function to print array elements { for(i = 0; i <5; i++) { document.writeln(a[i]); } document.write('before sorting array elements are - ' + <br>&apos;); print(); for(i = 0; i <5; i++) { for (j="0;" j < 5; j++) if(a[i] a[j]) temp="a[i];" a[i]="a[j];" a[j]="temp;" } document.write(' <br> After sorting array elements are - &apos; + &apos; <br>&apos;); print(); </5;></5;></pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-17.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in PHP.</p> <pre> <?php $a = array(2, 45, 88, 11, 5); function printArray($a) { for($i = 0; $i < 5; $i++) { print_r($a[$i]); echo ' '; } } echo 'Before sorting array elements are - <br>&apos;; printArray($a); for($i = 0; $i <5; $i++) { for ($j="0;" $j < 5; $j++) if($a[$i] $a[$j]) $temp="$a[$i];" $a[$i]="$a[$j];" $a[$j]="$temp;" } echo ' <br> After sorting array elements are - <br>&apos;; printArray($a); ?&gt; </5;></pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-18.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in python.</p> <pre> a = [35, 10, 31, 11, 26] print(&apos;Before sorting array elements are - &apos;) for i in a: print(i, end = &apos; &apos;) for i in range(0,len(a)): for j in range(i+1,len(a)): if a[j] <a[i]: temp="a[j]" a[j]="a[i]" a[i]="temp" print('
after sorting array elements are - ') for i in a: print(i, end=" " ) < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-19.webp" alt="Bubble sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the algorithm&apos;s complexity, working, optimized form, and implementation in different programming languages.</p> <hr></a[i]:></pre></n;></pre></n;></pre></n;></pre></n;>

Вихід

програма: Напишіть програму для реалізації бульбашкового сортування в PHP.

 <?php $a = array(2, 45, 88, 11, 5); function printArray($a) { for($i = 0; $i < 5; $i++) { print_r($a[$i]); echo \' \'; } } echo \'Before sorting array elements are - <br>&apos;; printArray($a); for($i = 0; $i <5; $i++) { for ($j="0;" $j < 5; $j++) if($a[$i] $a[$j]) $temp="$a[$i];" $a[$i]="$a[$j];" $a[$j]="$temp;" } echo \' <br> After sorting array elements are - <br>&apos;; printArray($a); ?&gt; </5;>