Bubble Sort algoritmus

Ebben az oktatóanyagban megtudhatja, hogyan működik a buborék rendezése. Ezenkívül találhat működő példákat a buborékok rendezésére C, C ++, Java és Python.

A Bubble sort olyan algoritmus, amely összehasonlítja a szomszédos elemeket és felcseréli a pozícióikat, ha nem a kívánt sorrendben vannak. A sorrend lehet növekvő vagy csökkenő.

Hogyan működik a Bubble Sort?

Az első indexből kiindulva hasonlítsa össze az első és a második elemet. Ha az első elem nagyobb, mint a második elem, akkor felcserélik őket.
Most hasonlítsa össze a második és a harmadik elemet. Cserélje ki őket, ha nincsenek rendben.
A fenti folyamat az utolsó elemig tart. Hasonlítsa össze a szomszédos elemeket
Ugyanez a folyamat zajlik a fennmaradó iterációknál is. Minden iteráció után a rendezés nélküli elemek közül a legnagyobb elem kerül a végére.
Minden egyes iterációban az összehasonlítás az utolsó rendezetlen elemig történik.
A tömb rendezése akkor történik, amikor az összes nem rendezett elem a megfelelő helyzetbe kerül. A szomszédos elemek összehasonlítása A szomszédos elemek összehasonlítása A szomszédos elemek összehasonlítása

Bubble Sort algoritmus

 bubbleSort (tömb) i rightElementre cserélje a leftElement és rightElement végét a bubbleSort

Példák Python, Java és C / C ++

Python Java C C ++

 # Bubble sort in Python def bubbleSort(array): # run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) data = (-2, 45, 0, 11, -9) bubbleSort(data) print('Sorted Array in Asc ending Order:') print(data)

 // Bubble sort in Java import java.util.Arrays; class BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) for (int j = 0; j  to array(j + 1)) ( // swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; ) ) // driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) )

 // Bubble sort in C #include void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i " to " array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printArray(data, size); )

 // Bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i to array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )

Optimalizált Bubble Sort

A fenti kódban minden lehetséges összehasonlítás akkor is megtörténik, ha a tömb már rendezve van. Növeli a végrehajtási időt.

A kód optimalizálható egy extra változó bevezetésével. Minden iteráció után, ha akkor nem történik cserélés, nincs szükség további ciklusok végrehajtására.

Ilyen esetben a váltott változó értéke hamis. Így megakadályozhatjuk a további iterációkat.

Az optimalizált buborék-rendezés algoritmusa

 bubbleSort (tömb) felcserélve <- false for i rightElement swap leftElement és rightElement swapped <- true end bubbleSort

Optimalizált buborék válogatási példák

Python Java C C +

 # Optimized bubble sort in python def bubbleSort(array): # Run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): # swapped keeps track of swapping swapped = True for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # Swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) swapped = False # If there is not swapping in the last swap, then the array is already sorted. if swapped: break data = (-2, 45, 0, 11, -9) bubbleSort(data) print('Sorted Array in Ascending Order:') print(data)

 // Optimized bubble sort in Java import java.util.Arrays; class BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) ( // swapped keeps track of swapping boolean swapped = true; for (int j = 0; j  to array(j + 1)) ( // Swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; swapped = false; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == true) break; ) ) // Driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) )

 // Optimized bubble sort in C #include void bubbleSort(int arrayay(), int size) ( for (int step = 0; step < size - 1; ++step) ( // Swapped keeps track of swapping int swapped = 0; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i to arrayay(i + 1)) ( // Swap if greater is at the rear position int temp = arrayay(i); arrayay(i) = arrayay(i + 1); arrayay(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printarrayay(int arrayay(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", arrayay(i)); ) printf(""); ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printarrayay(data, size); )

 // Optimized bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( for (int step = 0; step < size - 1; ++step) (

  // Run loops two times: one for walking throught the array // and the other for comparison int swapped = 0; for (int i = 0; i to array(i + 1)) ( // Swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )

Bonyolultság

A Bubble Sort az egyik legegyszerűbb rendezési algoritmus. Két hurok valósul meg az algoritmusban.

Ciklus	Összehasonlítások száma
1	(n-1)
2.	(n-2)
3	(n-3)
….	…
utolsó	1

Az összehasonlítások száma: (n - 1) + (n - 2) + (n - 3) +… + 1 = n (n - 1) / 2 majdnem megegyezik n ^2-vel

Komplexitás: O (n ² )

Ezenkívül elemezhetjük a bonyolultságot a hurkok számának egyszerű megfigyelésével. 2 hurok van, tehát a bonyolultságn*n = n²

Időkomplexumok:

Legrosszabb eset komplexitás: Ha növekvő sorrendben akarunk rendezni, és a tömb csökkenő sorrendben van, akkor a legrosszabb eset következik be.O(n²)
Legjobb bonyolultság:O(n)
Ha a tömb már rendezve van, akkor nincs szükség rendezésre.
Átlagos esetbonyolultság: Akkor fordul elő, amikor a tömb elemei összetévesztett sorrendben vannak (sem emelkedő, sem csökkenő).O(n²)