BUBORÉKOS RENDEZÉS - DS OKTATÓANYAG

Ebben a cikkben a buborékrendezési algoritmust tárgyaljuk. A buborékos válogatás művelete a legegyszerűbb. Ez a cikk nagyon hasznos és érdekes lesz a hallgatók számára, mivel vizsgáik során felmerülhet a buborék-rendezési kérdés. Ezért fontos a téma megvitatása.

mátrixszorzás c-ben

A buborékos rendezés a szomszédos elemek ismételt cseréjére működik, amíg azok nem a kívánt sorrendben vannak. Buborékos rendezésnek nevezik, mert a tömbelemek mozgása olyan, mint a légbuborékok mozgása a vízben. A vízben lévő buborékok a felszínre emelkednek; hasonlóképpen a buborékos rendezés tömbelemei minden iterációban a végére kerülnek.

Bár használata egyszerű, elsősorban oktatási eszközként használják, mivel a buborékrendezés teljesítménye a való világban gyenge. Nagy adathalmazokhoz nem alkalmas. A Bubble rendezés átlagos és legrosszabb összetettsége az Tovább²), ahol n számos elem.

A Bubble short főként ott használatos, ahol -

a komplexitás nem számít
egyszerű és rövid kódot részesítenek előnyben

Algoritmus

Tegyük fel, hogy az alábbi algoritmusban arr egy tömbje n elemeket. A feltételezett csere függvény az algoritmusban felcseréli az adott tömbelemek értékeit.

 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

A buborékrendezési algoritmus működése

Most pedig lássuk a buborékrendezési algoritmus működését.

A buborékrendezési algoritmus működésének megértéséhez vegyünk egy rendezetlen tömböt. Egy rövid és pontos tömböt veszünk, mivel tudjuk, hogy a buborékrendezés bonyolult Tovább²).

Legyen a tömb elemei -

Első Pass

A rendezés a kezdeti két elemtől indul. Hasonlítsa össze őket, hogy ellenőrizze, melyik a nagyobb.

Itt a 32 nagyobb, mint a 13 (32 > 13), tehát már rendezve van. Hasonlítsd össze a 32-t a 26-tal.

Itt a 26 kisebb, mint a 36. Tehát csere szükséges. Csere után az új tömb így fog kinézni:

Hasonlítsa össze a 32-t és a 35-öt.

Itt a 35 nagyobb, mint a 32. Tehát nincs szükség cserére, mivel már rendezve vannak.

Most az összehasonlítás 35 és 10 között lesz.

Itt a 10 kisebb, mint a 35, amelyek nincsenek rendezve. Tehát csere szükséges. Most elérjük a tömb végét. Az első lépés után a tömb a következő lesz:

Most lépjen a második iterációra.

Második Pass

Ugyanezt a folyamatot követjük a második iterációnál is.

karakterlánc

Itt a 10 kisebb, mint a 32. Tehát csere szükséges. Csere után a tömb a következő lesz:

Most lépjen a harmadik iterációra.

Harmadik Pass

Ugyanezt a folyamatot követjük a harmadik iterációnál is.

Itt a 10 kisebb, mint a 26. Tehát csere szükséges. Csere után a tömb a következő lesz:

Most lépjen a negyedik iterációra.

Negyedik passz

Hasonlóképpen, a negyedik iteráció után a tömb a következő lesz:

Ezért nincs szükség cserére, így a tömb teljesen rendezett.

Buborékos rendezés bonyolultsága

Most lássuk a buborékrendezés időbeli összetettségét a legjobb, az átlagos és a legrosszabb esetben. Látni fogjuk a buborékok rendezésének térbeli összetettségét is.

1. Időbonyolultság

Ügy	Idő összetettsége
Legjobb eset	Tovább)
Átlagos eset	Tovább²)
Legrosszabb esetben	Tovább²)

Tovább).

Tovább²).

2. A tér összetettsége

A tér összetettsége	O(1)
Stabil	IGEN

A buborékrendezés térkomplexitása O(1). Ez azért van így, mert a buborékos rendezésben egy extra változóra van szükség a cseréhez.
Az optimalizált buborékrendezés térkomplexitása O(2). Ez azért van, mert az optimalizált buborékrendezésben két extra változóra van szükség.

Most beszéljük meg az optimalizált buborékrendezési algoritmust.

Optimalizált buborékrendezési algoritmus

A buborékos rendezési algoritmusban az összehasonlítások akkor is megtörténnek, ha a tömb már rendezve van. Emiatt a végrehajtási idő megnő.

A megoldáshoz egy extra változót használhatunk felcserélték. Be van állítva igaz ha a csere szükséges; ellenkező esetben a következőre van állítva hamis.

Hasznos lesz, ha egy iteráció után nincs szükség cserére, a változó értéke felcserélték lesz hamis. Ez azt jelenti, hogy az elemek már rendezve vannak, és nincs szükség további iterációkra.

Ez a módszer csökkenti a végrehajtási időt és optimalizálja a buborékok rendezését.

Algoritmus az optimalizált buborékrendezéshez

 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

Buborék rendezés megvalósítása

Most pedig lássuk a Bubble rendezési programokat különböző programozási nyelveken.

listnode java

Program: Írjon programot a buborékrendezés megvalósítására C nyelven.

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

Kimenet

Program: Írjon programot a buborékrendezés megvalósítására PHP-ben.

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