Boble sortering er den enkleste sorteringsalgoritme der fungerer ved gentagne gange at udskifte de tilstødende elementer, hvis de er i den forkerte rækkefølge. Denne algoritme er ikke egnet til store datasæt, da dens gennemsnitlige og worst-case tidskompleksitet er ret høj.
Boblesorteringsalgoritme
Anbefalet praksis Boblesortering Prøv det!I Bubble Sort algoritmen,
- kryds fra venstre og sammenlign tilstødende elementer, og det højere placeres i højre side.
- På denne måde flyttes det største element først til den yderste højre ende.
- Denne proces fortsættes derefter for at finde den næststørste og placere den og så videre, indtil dataene er sorteret.
Hvordan fungerer boblesortering?
Lad os forstå, hvordan boblesortering fungerer ved hjælp af følgende illustration:
ipconfig på Ubuntu
Input: arr[] = {6, 0, 3, 5}
Første pas:
Det største element placeres i sin korrekte position, dvs. slutningen af arrayet.
Boblesorteringsalgoritme: Anbringelse af det største element i den rigtige position
Andet pas:
Placer det næststørste element i den rigtige position
Boblesorteringsalgoritme: Anbringelse af det næststørste element i den rigtige position
Tredje pas:
Placer de resterende to elementer i deres rigtige positioner.
java generere tilfældige talBoblesorteringsalgoritme: Anbringelse af de resterende elementer på deres korrekte positioner
- Samlet nr. af pas: n-1
- Samlet nr. af sammenligninger: n*(n-1)/2
Implementering af Bubble Sort
Nedenfor er implementeringen af boblesorteringen. Det kan optimeres ved at stoppe algoritmen, hvis den indre løkke ikke forårsagede nogen swap.
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]); byttet = sand; } } // Hvis ikke to elementer blev byttet // af indre løkke, så break if (swapped == false) break; } } // Funktion til at udskrive et array void printArray(int arr[], int size) { int i; for (i = 0; i< 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]); byttet = sand; } } // Hvis ikke to elementer blev byttet med indre løkke, // så break if (swapped == false) break; } } // Funktion til at udskrive et array void printArray(int arr[], int size) { int i; for (i = 0; i< 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]) { // Skift arr[j] og arr[j+1] temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; byttet = sand; } } // Hvis ikke to elementer var // byttet med indre løkke, så break if (swapped == false) break; } } // Funktion til at udskrive et array statisk void printArray(int arr[], int size) { int i; for (i = 0; i< 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 = Sand hvis (swapped == Falsk): brud # Driverkode for at teste ovenfor hvis __navn__ == '__main__': arr = [64, 34, 25, 12, 22, 11, 90] bubbleSort(arr) print('Sorted array:') for i in range(len(arr)): print('%d' % arr[i], end=' ') # Denne kode er ændret af 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]) { // Skift arr[j] og arr[j+1] temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; byttet = sand; } } // Hvis ikke to elementer var // byttet med indre løkke, så break if (swapped == false) break; } } // Funktion til at udskrive et array statisk void printArray(int[] arr, int size) { int i; for (i = 0; i< 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]) { // Skift arr[j] og arr[j+1] temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; byttet = sand; } } // HVIS ikke to elementer var // byttet med indre løkke, så break if (byttet == falsk) break; } } // Funktion til at udskrive en array-funktion printArray(arr, size) { var i; for (i = 0; i< 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; $swapped = Sand; } } // Hvis ikke to elementer blev byttet // af indre løkke, så break if ($swapped == False) break; } } // Driverkode $arr = array(64, 34, 25, 12, 22, 11, 90); $len = sizeof($arr); bubbleSort($arr); echo 'Sorteret array:
'; for($i = 0; $i< $len; $i++) echo $arr[$i].' '; // This code is contributed by ChitraNayal. ?>> Produktion
Sorted array: 11 12 22 25 34 64 90>
Kompleksitetsanalyse af boblesortering :
Tidskompleksitet: PÅ2)
Hjælpeplads: O(1)
Fordele ved Bubble Sort:
- Boblesortering er let at forstå og implementere.
- Det kræver ikke yderligere hukommelsesplads.
- Det er en stabil sorteringsalgoritme, hvilket betyder, at elementer med samme nøgleværdi bevarer deres relative rækkefølge i det sorterede output.
Ulemper ved Bubble Sort:
- Boblesortering har en tidskompleksitet på O(N2), hvilket gør den meget langsom for store datasæt.
- Boblesortering er en sammenligningsbaseret sorteringsalgoritme, hvilket betyder, at det kræver en sammenligningsoperator for at bestemme den relative rækkefølge af elementer i inputdatasættet. Det kan begrænse effektiviteten af algoritmen i visse tilfælde.
Nogle ofte stillede spørgsmål relateret til Bubble Sort:
Hvad er grænsekassen for boblesortering?
Boblesortering tager minimum tid (rækkefølge af n), når elementer allerede er sorteret. Derfor er det bedst at kontrollere, om arrayet allerede er sorteret eller ej på forhånd, for at undgå O(N2) tidskompleksitet.
Sker sortering på plads i boblesortering?
Ja, Bubble sort udfører ombytning af tilstødende par uden brug af nogen større datastruktur. Derfor er boblesorteringsalgoritme en in-place algoritme.
streng til boolesk java
Er boblesorteringsalgoritmen stabil?
Ja, boblesorteringsalgoritmen er stabil.
Hvor bruges boblesorteringsalgoritmen?
På grund af sin enkelhed bruges boblesortering ofte til at introducere begrebet en sorteringsalgoritme. Inden for computergrafik er det populært for dets evne til at opdage en lille fejl (som et udskiftning af kun to elementer) i næsten-sorterede arrays og rette det med kun lineær kompleksitet (2n).
Eksempel: Det bruges i en polygonudfyldningsalgoritme, hvor afgrænsningslinjer er sorteret efter deres x-koordinat ved en specifik scanningslinje (en linje parallel med x-aksen), og med stigning i y deres rækkefølge ændres kun (to elementer er byttet om) i skæringspunkter mellem to linjer.
Relaterede artikler:
- Rekursiv boblesortering
- Kodningspraksis til sortering
- Quiz om Bubble Sort
- Kompleksitetsanalyse af boblesortering