СОРТИРАНЕ НА МЕХУРЧЕТА

В тази статия ще обсъдим алгоритъма за сортиране с мехурчета. Работната процедура на балонно сортиране е най-проста. Тази статия ще бъде много полезна и интересна за студентите, тъй като те може да се сблъскат със сортиране на мехурчета като въпрос на своите изпити. Така че е важно да обсъдим темата.

съдържа java метод

Сортирането с мехурчета работи върху многократната смяна на съседни елементи, докато не са в предвидения ред. Нарича се балонно сортиране, защото движението на елементите на масива е точно като движението на въздушни мехурчета във водата. Мехурчетата във водата се издигат на повърхността; по подобен начин, елементите на масива при балонно сортиране се придвижват до края при всяка итерация.

Въпреки че е лесен за използване, той се използва предимно като образователен инструмент, тъй като ефективността на балонното сортиране е лоша в реалния свят. Не е подходящ за големи набори от данни. Средната и най-лошата сложност на Bubble sort е На²), където н е редица елементи.

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

Работа на алгоритъма за сортиране с мехурчета

Сега нека видим работата на алгоритъма за сортиране с мехурчета.

За да разберем работата на алгоритъма за балонно сортиране, нека вземем несортиран масив. Ние вземаме кратък и точен масив, тъй като знаем сложността на балонното сортиране На²).

Нека елементите на масива са -

Първо преминаване

Сортирането ще започне от първите два елемента. Нека ги сравним, за да проверим кое е по-голямо.

Тук 32 е по-голямо от 13 (32 > 13), така че вече е сортирано. Сега сравнете 32 с 26.

Тук 26 е по-малко от 36. Така че се изисква размяна. След размяната новият масив ще изглежда така -

Сега сравнете 32 и 35.

Тук 35 е по-голямо от 32. Така че не е необходима размяна, тъй като те вече са сортирани.

Сега сравнението ще бъде между 35 и 10.

Тук 10 е по-малко от 35, които не са сортирани. Така че е необходима размяна. Сега стигаме до края на масива. След първото преминаване масивът ще бъде -

Сега преминете към втората итерация.

Второ преминаване

Същият процес ще бъде последван за второ повторение.

Тук 10 е по-малко от 32. Така че се изисква размяна. След размяната масивът ще бъде -

Сега преминете към третата итерация.

Трето преминаване

Същият процес ще бъде последван за трета итерация.

Тук 10 е по-малко от 26. Така че се изисква размяна. След размяната масивът ще бъде -

Сега преминете към четвъртата итерация.

Четвърто преминаване

По същия начин, след четвъртата итерация, масивът ще бъде -

alter добави колона oracle

Следователно не се изисква размяна, така че масивът е напълно сортиран.

Сложност на сортиране на мехурчета

Сега нека видим времевата сложност на балонното сортиране в най-добрия случай, средния случай и най-лошия случай. Ще видим и космическата сложност на балонното сортиране.

1. Времева сложност

Случай	Времева сложност
Най-добър случай	На)
Среден случай	На²)
Най-лошия случай	На²)

На).

На²).

2. Космическа сложност

Космическа сложност	О(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

Сега нека видим програмите на Bubble sort в различни езици за програмиране.

матрици в c програмирането

програма: Напишете програма за прилагане на балонно сортиране на език 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;>