Bubble Sort-algoritme

In deze tutorial leer je hoe bellen sorteren werkt. Ook vindt u voorbeelden van het sorteren van bellen in C, C ++, Java en Python.

Bubble sort is een algoritme dat de aangrenzende elementen vergelijkt en hun posities verwisselt als ze niet in de beoogde volgorde staan. De volgorde kan oplopend of aflopend zijn.

Hoe werkt Bubble Sort?

Vergelijk, uitgaande van de eerste index, het eerste en het tweede element. Als het eerste element groter is dan het tweede element, worden ze verwisseld.
Vergelijk nu het tweede en het derde element. Verwissel ze als ze niet in orde zijn.
Het bovenstaande proces gaat door tot het laatste element. Vergelijk de aangrenzende elementen
Hetzelfde proces gaat door voor de resterende iteraties. Na elke iteratie wordt het grootste element van de ongesorteerde elementen aan het einde geplaatst.
Bij elke iteratie vindt de vergelijking plaats tot aan het laatste ongesorteerde element.
De array wordt gesorteerd als alle ongesorteerde elementen op de juiste positie zijn geplaatst. Vergelijk de aangrenzende elementen Vergelijk de aangrenzende elementen Vergelijk de aangrenzende elementen

Bubble Sort-algoritme

 bubbleSort (array) voor i rightElement swap leftElement en rightElement end bubbleSort

Python, Java en C / C ++ voorbeelden

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

Geoptimaliseerde bubbelsortering

In de bovenstaande code worden alle mogelijke vergelijkingen gemaakt, zelfs als de array al is gesorteerd. Het verlengt de uitvoeringstijd.

De code kan worden geoptimaliseerd door een extra variabele swapped te introduceren. Als er na elke iteratie geen wisseling plaatsvindt, is het niet nodig om verdere lussen uit te voeren.

In dat geval wordt variabele swapped ingesteld op false. Zo kunnen we verdere iteraties voorkomen.

Algoritme voor geoptimaliseerde belsortering is

 bubbleSort (array) swapped <- false voor i rightElement swap leftElement en rightElement swapped <- true einde bubbleSort

Voorbeelden van geoptimaliseerde bellen sorteren

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

Complexiteit

Bubble Sort is een van de eenvoudigste sorteeralgoritmen. Er zijn twee lussen geïmplementeerd in het algoritme.

Fiets	Aantal vergelijkingen
1e	(n-1)
2e	(n-2)
3e	(n-3)
….	…
laatste	1

Aantal vergelijkingen: (n - 1) + (n - 2) + (n - 3) +… + 1 = n (n - 1) / 2 is bijna gelijk aan n ²

Complexiteit: O (n ² )

We kunnen ook de complexiteit analyseren door simpelweg het aantal lussen te observeren. Er zijn 2 loops, dus de complexiteit isn*n = n²

Tijdscomplexiteit:

Complexiteit in het ergste geval: Als we in oplopende volgorde willen sorteren en de array is in aflopende volgorde, dan doet zich het ergste geval voor.O(n²)
Complexiteit in het beste geval:O(n)
als de array al is gesorteerd, hoeft deze niet te worden gesorteerd.
Gemiddelde hoofdlettercomplexiteit: treedt op wanneer de elementen van de array in een door elkaar gegooide volgorde staan (noch oplopend noch aflopend).O(n²)