Bu yazımızda Kabarcık Sıralama Algoritmasını tartışacağız. Kabarcık sıralamanın çalışma prosedürü en basittir. Bu makale, sınavlarında soru olarak kabarcık sıralamayla karşılaşabilecekleri için öğrenciler için çok yararlı ve ilginç olacaktır. Bu nedenle konuyu tartışmak önemlidir.

bir dizini yeniden adlandırma

Kabarcık sıralaması, bitişik öğelerin amaçlanan sırada olmayana kadar tekrar tekrar değiştirilmesiyle çalışır. Buna kabarcık sıralama denir çünkü dizi elemanlarının hareketi sudaki hava kabarcıklarının hareketine benzer. Sudaki kabarcıklar yüzeye çıkar; benzer şekilde, kabarcık sıralamadaki dizi öğeleri her yinelemede sonuna doğru hareket eder.

Kullanımı basit olmasına rağmen, kabarcık sıralamanın performansı gerçek dünyada zayıf olduğundan öncelikle bir eğitim aracı olarak kullanılır. Büyük veri setleri için uygun değildir. Kabarcık sıralamasının ortalama ve en kötü durum karmaşıklığı Açık²), Neresi N bir dizi öğedir.

Kabarcık kısa çoğunlukla aşağıdaki durumlarda kullanılır:

• karmaşıklık önemli değil
• basit ve kısa kod tercih edilir

Algoritma

Aşağıda verilen algoritmada, varsayalım varış bir dizidir N elementler. Varsayılan takas Algoritmadaki işlev, verilen dizi öğelerinin değerlerini değiştirecektir.

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

Kabarcık sıralama algoritmasının çalışması

Şimdi Kabarcık Sıralama Algoritmasının çalışmasına bakalım.

Kabarcık sıralama algoritmasının çalışmasını anlamak için sıralanmamış bir diziyi ele alalım. Kabarcık sıralamanın karmaşıklığını bildiğimiz için kısa ve doğru bir dizi alıyoruz. Açık²).

Dizinin elemanları şöyle olsun:

İlk geçiş

Sıralama ilk iki öğeden başlayacaktır. Hangisinin daha büyük olduğunu kontrol etmek için bunları karşılaştıralım.

Burada 32, 13'ten büyüktür (32 > 13), dolayısıyla zaten sıralanmıştır. Şimdi 32 ile 26'yı karşılaştırın.

Burada 26, 36'dan küçüktür. Dolayısıyla yer değiştirme gerekir. Yeni dizi değiştirildikten sonra şöyle görünecek:

Şimdi 32 ile 35'i karşılaştırın.

Burada 35, 32'den büyüktür. Yani zaten sıralanmış oldukları için yer değiştirmeye gerek yoktur.

Şimdi karşılaştırma 35 ile 10 arasında olacak.

nfa'dan dfa'ya dönüştürme

Burada 10, sıralanmamış 35'ten küçüktür. Yani takas şart. Artık dizinin sonuna ulaşıyoruz. İlk geçişten sonra dizi şöyle olacaktır:

Şimdi ikinci yinelemeye geçin.

İkinci Geçiş

İkinci iterasyonda da aynı süreç izlenecektir.

Burada 10, 32'den küçüktür. Dolayısıyla yer değiştirme gerekir. Değiştirmeden sonra dizi şöyle olacaktır:

Şimdi üçüncü yinelemeye geçin.

Üçüncü Geçiş

Üçüncü iterasyonda da aynı süreç izlenecektir.

Burada 10, 26'dan küçüktür. Dolayısıyla yer değiştirme gerekir. Değiştirmeden sonra dizi şöyle olacaktır:

Şimdi dördüncü yinelemeye geçin.

Dördüncü geçiş

Benzer şekilde, dördüncü yinelemeden sonra dizi şöyle olacaktır:

Dolayısıyla herhangi bir değiştirmeye gerek yoktur, dolayısıyla dizi tamamen sıralanır.

Kabarcık sıralama karmaşıklığı

Şimdi en iyi durumda, ortalama durumda ve en kötü durumda kabarcık sıralamanın zaman karmaşıklığını görelim. Ayrıca kabarcık sıralamanın uzay karmaşıklığını da göreceğiz.

1. Zaman Karmaşıklığı

En İyi Durum Karmaşıklığı -Sıralama gerekmediğinde oluşur, yani dizi zaten sıralanmıştır. Kabarcık sıralamanın en iyi durum zaman karmaşıklığı Açık). Ortalama Vaka Karmaşıklığı -Dizi öğeleri, düzgün şekilde artan ve düzgün şekilde alçalan olmayan, karışık bir düzende olduğunda ortaya çıkar. Kabarcık sıralamanın ortalama vaka süresi karmaşıklığı Açık²). En Kötü Durum Karmaşıklığı -Dizi elemanlarının ters sırada sıralanması gerektiğinde ortaya çıkar. Bu, dizi elemanlarını artan sırada sıralamanız gerektiğini, ancak elemanlarının azalan sırada olduğunu varsayalım anlamına gelir. Kabarcık sıralamanın en kötü zaman karmaşıklığı Açık²).

2. Uzayın Karmaşıklığı

• Kabarcık sıralamasının uzay karmaşıklığı O(1)'dir. Bunun nedeni, kabarcık sıralamasında takas için ekstra bir değişkenin gerekli olmasıdır.
• Optimize edilmiş kabarcık sıralamanın uzay karmaşıklığı O(2)'dir. Bunun nedeni, optimize edilmiş kabarcık sıralamasında iki ekstra değişkenin gerekli olmasıdır.

Şimdi optimize edilmiş kabarcık sıralama algoritmasını tartışalım.

Optimize Edilmiş Kabarcık Sıralama Algoritması

Kabarcık sıralama algoritmasında, dizi zaten sıralanmış olsa bile karşılaştırmalar yapılır. Bu nedenle yürütme süresi artar.

Bunu çözmek için ekstra bir değişken kullanabiliriz takas edildi. Şu şekilde ayarlandı: doğru takas gerektiriyorsa; aksi halde şu şekilde ayarlanır: YANLIŞ.

Bir yinelemeden sonra, herhangi bir değişiklik gerekmiyorsa, değişkenin değerinin ayarlanması yararlı olacaktır. takas edildi olacak YANLIŞ. Bu, öğelerin zaten sıralandığı ve daha fazla yinelemeye gerek olmadığı anlamına gelir.

Bu yöntem yürütme süresini kısaltacak ve aynı zamanda kabarcık sıralamasını da optimize edecektir.

Optimize edilmiş kabarcık sıralama algoritması

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

Kabarcık sıralamasının uygulanması

Şimdi farklı programlama dillerinde Bubble sort programlarını görelim.

liste düğümü java

Program: C dilinde kabarcık sıralamayı uygulayan bir program yazın.

 #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;>

Çıktı

Program: PHP'de kabarcık sıralamayı uygulayan bir program yazın.

 <?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;>

Çıktı

Program: Python'da kabarcık sıralamayı uygulayan bir program yazın.

 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]:>