KABARCIK SIRALAMASI - DS EĞITIMI

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] &gt; 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ığı

Dava	Zaman Karmaşıklığı
En iyi senaryo	Açık)
Ortalama Durum	Açık²)
En kötü durumda	Açık²)

Açık).

Açık²).

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

Uzay Karmaşıklığı	Ç(1)
Stabil	EVET

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] &gt; 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]:>