Bellen sorteren is het eenvoudigst sorteeralgoritme dat werkt door de aangrenzende elementen herhaaldelijk te verwisselen als ze in de verkeerde volgorde staan. Dit algoritme is niet geschikt voor grote datasets, omdat de gemiddelde tijdscomplexiteit en in het slechtste geval vrij hoog is.
Bellensorteeralgoritme
Aanbevolen oefening Bellen sorteren Probeer het!In het Bubble Sort-algoritme
- doorkruis vanaf links en vergelijk aangrenzende elementen en de hogere wordt aan de rechterkant geplaatst.
- Op deze manier wordt het grootste element eerst naar het meest rechtse uiteinde verplaatst.
- Dit proces wordt vervolgens voortgezet om de op één na grootste te vinden en deze te plaatsen, enzovoort, totdat de gegevens zijn gesorteerd.
Hoe werkt het sorteren van bellen?
Laten we de werking van het sorteren van bellen begrijpen met behulp van de volgende illustratie:
Invoer: arr[] = {6, 0, 3, 5}
Eerste Paas:
Het grootste element wordt op de juiste positie geplaatst, d.w.z. op het einde van de array.
Bellensorteeralgoritme: Plaats het grootste element op de juiste positie
Tweede pas:
Plaats het op één na grootste element op de juiste positie
Bellensorteeralgoritme: Plaats het op een na grootste element op de juiste positie
Derde pas:
Plaats de overige twee elementen op de juiste positie.
Bubble Sort Algorithm: Plaats de resterende elementen op de juiste posities
- Totaal nee. Aantal passen: n-1
- Totaal nee. van vergelijkingen: n*(n-1)/2
Implementatie van bellensortering
Hieronder ziet u de implementatie van de bellensoort. Het kan worden geoptimaliseerd door het algoritme te stoppen als de binnenste lus geen enkele swap heeft veroorzaakt.
C++ // Optimized implementation of Bubble sort #include using namespace std; // An optimized version of Bubble Sort void bubbleSort(int arr[], int n) { int i, j; bool swapped; for (i = 0; i < n - 1; i++) { swapped = false; for (j = 0; j < n - i - 1; j++) { if (arr[j]>arr[j + 1]) { swap(arr[j], arr[j + 1]); verwisseld = waar; } } // Als er geen twee elementen zijn verwisseld // door de binnenste lus, dan break if (swapped == false) break; } } // Functie voor het afdrukken van een array void printArray(int arr[], int size) { int i; voor (i = 0; ik< size; i++) cout << ' ' << arr[i]; } // Driver program to test above functions int main() { int arr[] = { 64, 34, 25, 12, 22, 11, 90 }; int N = sizeof(arr) / sizeof(arr[0]); bubbleSort(arr, N); cout << 'Sorted array:
'; printArray(arr, N); return 0; } // This code is contributed by shivanisinghss2110> C // Optimized implementation of Bubble sort #include #include void swap(int* xp, int* yp) { int temp = *xp; *xp = *yp; *yp = temp; } // An optimized version of Bubble Sort void bubbleSort(int arr[], int n) { int i, j; bool swapped; for (i = 0; i < n - 1; i++) { swapped = false; for (j = 0; j < n - i - 1; j++) { if (arr[j]>arr[j + 1]) { swap(&arr[j], &arr[j + 1]); verwisseld = waar; } } // Als er geen twee elementen zijn verwisseld door de binnenste lus, // dan break if (swapped == false) break; } } // Functie voor het afdrukken van een array void printArray(int arr[], int size) { int i; voor (i = 0; ik< size; i++) printf('%d ', arr[i]); } // Driver program to test above functions int main() { int arr[] = { 64, 34, 25, 12, 22, 11, 90 }; int n = sizeof(arr) / sizeof(arr[0]); bubbleSort(arr, n); printf('Sorted array:
'); printArray(arr, n); return 0; }> Java // Optimized java implementation of Bubble sort import java.io.*; class GFG { // An optimized version of Bubble Sort static void bubbleSort(int arr[], int n) { int i, j, temp; boolean swapped; for (i = 0; i < n - 1; i++) { swapped = false; for (j = 0; j < n - i - 1; j++) { if (arr[j]>arr[j + 1]) {// Wissel arr[j] en arr[j+1] temp = arr[j] om; arr[j] = arr[j + 1]; arr[j + 1] = temperatuur; verwisseld = waar; } } // Als er geen twee elementen // verwisseld zijn door de binnenste lus, dan break if (verwisseld == false) break; } } // Functie voor het afdrukken van een array static void printArray(int arr[], int size) { int i; voor (i = 0; ik< size; i++) System.out.print(arr[i] + ' '); System.out.println(); } // Driver program public static void main(String args[]) { int arr[] = { 64, 34, 25, 12, 22, 11, 90 }; int n = arr.length; bubbleSort(arr, n); System.out.println('Sorted array: '); printArray(arr, n); } } // This code is contributed // by Nikita Tiwari.> Python3 # Optimized Python program for implementation of Bubble Sort def bubbleSort(arr): n = len(arr) # Traverse through all array elements for i in range(n): swapped = False # Last i elements are already in place for j in range(0, n-i-1): # Traverse the array from 0 to n-i-1 # Swap if the element found is greater # than the next element if arr[j]>arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] swapped = True if (swapped == False): break # Stuurprogrammacode om hierboven te testen if __name__ == '__main__': arr = [64, 34, 25, 12, 22, 11, 90] bubbleSort(arr) print('Gesorteerde array:') voor i binnen bereik(len(arr)): print('%d' % arr[i], end=' ') # Deze code is aangepast door Suraj krushna Yadav> C# // Optimized C# implementation of Bubble sort using System; class GFG { // An optimized version of Bubble Sort static void bubbleSort(int[] arr, int n) { int i, j, temp; bool swapped; for (i = 0; i < n - 1; i++) { swapped = false; for (j = 0; j < n - i - 1; j++) { if (arr[j]>arr[j + 1]) {// Wissel arr[j] en arr[j+1] temp = arr[j] om; arr[j] = arr[j + 1]; arr[j + 1] = temperatuur; verwisseld = waar; } } // Als er geen twee elementen // verwisseld zijn door de binnenste lus, dan break if (verwisseld == false) break; } } // Functie voor het afdrukken van een array static void printArray(int[] arr, int size) { int i; voor (i = 0; ik< size; i++) Console.Write(arr[i] + ' '); Console.WriteLine(); } // Driver method public static void Main() { int[] arr = { 64, 34, 25, 12, 22, 11, 90 }; int n = arr.Length; bubbleSort(arr, n); Console.WriteLine('Sorted array:'); printArray(arr, n); } } // This code is contributed by Sam007> Javascript // Optimized javaScript implementation // of Bubble sort // An optimized version of Bubble Sort function bubbleSort(arr, n) { var i, j, temp; var swapped; for (i = 0; i < n - 1; i++) { swapped = false; for (j = 0; j < n - i - 1; j++) { if (arr[j]>arr[j + 1]) {// Wissel arr[j] en arr[j+1] temp = arr[j] om; arr[j] = arr[j + 1]; arr[j + 1] = temperatuur; verwisseld = waar; } } // ALS er geen twee elementen zijn // verwisseld door de binnenste lus, dan break if (verwisseld == false) break; } } // Functie om een array-functie printArray(arr, size) { var i; voor (i = 0; ik< size; i++) console.log(arr[i] + ' '); } // Driver program var arr = [ 64, 34, 25, 12, 22, 11, 90 ]; var n = arr.length; bubbleSort(arr, n); console.log('Sorted array: '); printArray(arr, n); // This code is contributed shivanisinghss2110> PHP // PHP Optimized implementation // of Bubble sort // An optimized version of Bubble Sort function bubbleSort(&$arr) { $n = sizeof($arr); // Traverse through all array elements for($i = 0; $i < $n; $i++) { $swapped = False; // Last i elements are already // in place for ($j = 0; $j < $n - $i - 1; $j++) { // Traverse the array from 0 to // n-i-1. Swap if the element // found is greater than the // next element if ($arr[$j]>$arr[$j+1]) { $t = $arr[$j]; $arr[$j] = $arr[$j+1]; $arr[$j+1] = $t; $geruild = Waar; } } // Als er geen twee elementen zijn verwisseld // door de binnenste lus, dan break if ($swapped == False) break; } } // Stuurprogrammacode $arr = array(64, 34, 25, 12, 22, 11, 90); $len = groottevan($arr); bubbleSort($arr); echo 'Gesorteerde array:
'; voor($i = 0; $i< $len; $i++) echo $arr[$i].' '; // This code is contributed by ChitraNayal. ?>> Uitvoer
Sorted array: 11 12 22 25 34 64 90>
Complexiteitsanalyse van bellensortering :
Tijdcomplexiteit: OP2)
Hulpruimte: O(1)
Voordelen van bellensortering:
- Bellen sorteren is gemakkelijk te begrijpen en te implementeren.
- Er is geen extra geheugenruimte voor nodig.
- Het is een stabiel sorteeralgoritme, wat betekent dat elementen met dezelfde sleutelwaarde hun relatieve volgorde in de gesorteerde uitvoer behouden.
Nadelen van bellensortering:
- Het sorteren van bellen heeft een tijdscomplexiteit van O(N2) wat het erg traag maakt voor grote datasets.
- Bubble sort is een op vergelijkingen gebaseerd sorteeralgoritme, wat betekent dat er een vergelijkingsoperator voor nodig is om de relatieve volgorde van elementen in de invoergegevensset te bepalen. Het kan in bepaalde gevallen de efficiëntie van het algoritme beperken.
Enkele veelgestelde vragen over het sorteren van bellen:
Wat is het grensgeval voor het sorteren van bellen?
Het sorteren van bellen kost een minimale tijd (volgorde van n) wanneer de elementen al zijn gesorteerd. Daarom is het het beste om vooraf te controleren of de array al is gesorteerd of niet, om O(N2) tijdcomplexiteit.
Vindt sortering plaats in Bubble sort?
Ja, Bubble sort voert het verwisselen van aangrenzende paren uit zonder het gebruik van een grote datastructuur. Daarom is het Bubble-sorteeralgoritme een in-place algoritme.
Is het Bubble-sorteeralgoritme stabiel?
Ja, het algoritme voor het sorteren van bellen is stabiel.
Waar wordt het Bubble-sorteeralgoritme gebruikt?
Vanwege zijn eenvoud wordt bellensortering vaak gebruikt om het concept van een sorteeralgoritme te introduceren. In computergraphics is het populair vanwege zijn vermogen om een kleine fout (zoals het verwisselen van slechts twee elementen) in bijna gesorteerde arrays te detecteren en deze met alleen lineaire complexiteit (2n) te repareren.
Voorbeeld: Het wordt gebruikt in een algoritme voor het vullen van polygonen, waarbij grenslijnen worden gesorteerd op hun x-coördinaat op een specifieke scanlijn (een lijn evenwijdig aan de x-as), en bij het verhogen van y verandert hun volgorde alleen (twee elementen worden verwisseld). op de snijpunten van twee lijnen.
Gerelateerde artikelen:
- Recursieve bellensortering
- Codeeroefening voor sorteren
- Quiz over het sorteren van bellen
- Complexiteitsanalyse van bellensortering