Algoritmul de sortare cu bule

În acest tutorial, veți afla cum funcționează sortarea cu bule. De asemenea, veți găsi exemple de lucru de sortare cu bule în C, C ++, Java și Python.

Sortarea cu bule este un algoritm care compară elementele adiacente și le schimbă pozițiile dacă nu sunt în ordinea dorită. Ordinea poate fi crescătoare sau descendentă.

Cum funcționează sortarea cu bule?

Începând de la primul index, comparați primul și al doilea element. Dacă primul element este mai mare decât al doilea element, acestea sunt schimbate.
Acum, comparați al doilea și al treilea element. Schimbați-le dacă nu sunt în ordine.
Procesul de mai sus continuă până la ultimul element. Comparați elementele adiacente
Același proces se întâmplă și pentru iterațiile rămase. După fiecare iterație, cel mai mare element dintre elementele nesortate este plasat la sfârșit.
În fiecare iterație, comparația are loc până la ultimul element nesortat.
Matricea este sortată atunci când toate elementele nesortate sunt plasate în pozițiile lor corecte. Comparați elementele adiacente Comparați elementele adiacente Comparați elementele adiacente

Algoritmul de sortare cu bule

 bubbleSort (matrice) pentru i rightElement swap leftElement și rightElement sfârșesc bubbleSort

Exemple Python, Java și 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); )

Sortare cu bule optimizată

În codul de mai sus, toate comparațiile posibile sunt făcute chiar dacă matricea este deja sortată. Crește timpul de execuție.

Codul poate fi optimizat prin introducerea unei variabile suplimentare schimbate. După fiecare iterație, dacă nu are loc nicio schimbare, nu este necesar să mai efectuați bucle.

Într-un astfel de caz, variabila swapped este setată false. Astfel, putem preveni iterații suplimentare.

Algoritmul pentru sortarea optimizată a bulelor este

 bubbleSort (array) swapped <- false for i rightElement swap leftElement și rightElement swapped <- true end bubbleSort

Exemple de sortare optimizată cu bule

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

Complexitate

Bubble Sort este unul dintre cei mai simpli algoritmi de sortare. Două bucle sunt implementate în algoritm.

Ciclu	Numărul de comparații
Primul	(n-1)
Al 2-lea	(n-2)
A treia	(n-3)
….	…
ultimul	1

Numărul de comparații: (n - 1) + (n - 2) + (n - 3) +… + 1 = n (n - 1) / 2 aproape egal cu n ²

Complexitate: O (n ² )

De asemenea, putem analiza complexitatea prin simpla observare a numărului de bucle. Există 2 bucle, deci complexitatea esten*n = n²

Complexități de timp:

Cel mai prost caz de complexitate: Dacă vrem să sortăm în ordine crescătoare și matricea este în ordine descrescătoare, atunci apare cel mai rău caz.O(n²)
Complexitatea celui mai bun caz:O(n)
Dacă matricea este deja sortată, atunci nu este nevoie de sortare.
Complexitatea medie a cazurilor: apare atunci când elementele matricei sunt în ordine amestecată (nici crescătoare, nici descendentă).O(n²)

Complexitate spațială:
complexitatea spațiului se O(1)datorează faptului că se utilizează o temperatură variabilă suplimentară pentru schimbare.

În algoritmul optimizat, variabila schimbată se adaugă la complexitatea spațiului, devenind astfel O(2).