Burbuļu kārtošana ir visvienkāršākā šķirošanas algoritms kas darbojas, atkārtoti apmainot blakus esošos elementus, ja tie atrodas nepareizā secībā. Šis algoritms nav piemērots lielām datu kopām, jo tā vidējā un sliktākā gadījuma laika sarežģītība ir diezgan augsta.
Burbuļu kārtošanas algoritms
Ieteicamā prakse burbuļu kārtošana Izmēģiniet to!Bubble Sort algoritmā
- šķērsojiet no kreisās puses un salīdziniet blakus esošos elementus, un augstākais tiek novietots labajā pusē.
- Tādā veidā lielākais elements vispirms tiek pārvietots uz galējo galu.
- Pēc tam šis process tiek turpināts, lai atrastu otro lielāko un novietotu to un tā tālāk, līdz dati tiek sakārtoti.
Kā darbojas burbuļu kārtošana?
Ļaujiet mums saprast burbuļu kārtošanas darbību, izmantojot šādu ilustrāciju:
Ievade: arr[] = {6, 0, 3, 5}
Pirmā caurlaide:
Lielākais elements tiek novietots pareizajā vietā, t.i., masīva galā.
dateformat.format javaBurbuļu kārtošanas algoritms: lielākā elementa novietošana pareizajā vietā
Otrā caurlaide:
Novietojiet otro lielāko elementu pareizajā vietā
Burbuļu kārtošanas algoritms: otrā lielākā elementa novietošana pareizajā pozīcijā
Trešā caurlaide:
Novietojiet atlikušos divus elementus pareizajās pozīcijās.
Burbuļu kārtošanas algoritms: atlikušo elementu novietošana pareizajās pozīcijās
- Kopējais Nr. no caurlaidēm: n-1
- Kopējais Nr. no salīdzinājumiem: n*(n-1)/2
Bubble Sort ieviešana
Zemāk ir parādīta burbuļu kārtošanas ieviešana. To var optimizēt, apturot algoritmu, ja iekšējā cilpa neizraisīja mijmaiņu.
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]) { mijmaiņas (arr[j], arr[j + 1]); apmainīts = patiess; } } // Ja ar iekšējo cilpu netika apmainīti divi elementi //, tad break if (swapped == false) break; } } // Funkcija masīva drukāšanai void printArray(int arr[], int size) { int i; par (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]) { mijmaiņas (&arr[j], &arr[j + 1]); apmainīts = patiess; } } // Ja ar iekšējo cilpu netika apmainīti divi elementi, // tad break if (swapped == false) break; } } // Funkcija masīva drukāšanai void printArray(int arr[], int size) { int i; par (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]) { // Apmainīt arr[j] un arr[j+1] temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; apmainīts = patiess; } } // Ja ar iekšējo cilpu netika // apmainīti divi elementi, tad break if (swapped == false) break; } } // Funkcija masīva drukāšanai static void printArray(int arr[], int size) { int i; par (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] apmainīts = patiess, ja (samainīts == False): pārtraukums # Vadītāja kods, lai pārbaudītu iepriekš, ja __name__ == '__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=' ') # Šo kodu ir modificējis 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]) { // Apmainīt arr[j] un arr[j+1] temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; apmainīts = patiess; } } // Ja ar iekšējo cilpu netika // apmainīti divi elementi, tad break if (swapped == false) break; } } // Funkcija masīva drukāšanai static void printArray(int[] arr, int size) { int i; par (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]) { // Apmainīt arr[j] un arr[j+1] temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; apmainīts = patiess; } } // JA ar iekšējo cilpu netika // apmainīti divi elementi, tad pārtraukums if (swapped == false) break; } } // Funkcija masīva funkcijas drukāšanai printArray(arr, size) { var i; par (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; $swap = True; } } // Ja ar iekšējo cilpu netika apmainīti divi elementi //, tad break if ($swaped == False) break; } } // Draivera kods $arr = array(64, 34, 25, 12, 22, 11, 90); $len = izmērsof($arr); bubbleSort($arr); echo 'Kārtots masīvs:
'; for($i = 0; $i< $len; $i++) echo $arr[$i].' '; // This code is contributed by ChitraNayal. ?>>>
Izvade Laika sarežģītība: O(N2)
Palīgtelpa: O(1) Burbuļu šķirošanas priekšrocības:
- Burbuļu kārtošana ir viegli saprotama un īstenojama.
- Tam nav nepieciešama papildu atmiņas vieta.
- Tas ir stabils kārtošanas algoritms, kas nozīmē, ka elementi ar vienādu atslēgas vērtību saglabā savu relatīvo secību sakārtotajā izvadē.
Burbuļu šķirošanas trūkumi:
- Burbuļu kārtošanas laika sarežģītība ir O(N2), kas padara to ļoti lēnu lielām datu kopām.
- Burbuļu kārtošana ir uz salīdzināšanu balstīts kārtošanas algoritms, kas nozīmē, ka tam ir nepieciešams salīdzināšanas operators, lai noteiktu elementu relatīvo secību ievades datu kopā. Atsevišķos gadījumos tas var ierobežot algoritma efektivitāti.
Daži FAQ saistībā ar burbuļu kārtošanu:
Kāds ir burbuļa šķirošanas robežgadījums?
Burbuļu kārtošana aizņem minimālu laiku (n-kārtība), kad elementi jau ir sakārtoti. Tāpēc vislabāk ir pārbaudīt, vai masīvs jau ir sakārtots vai nav iepriekš, lai izvairītos no O(N2) laika sarežģītība.
Vai Bubble sortēšanas gadījumā šķirošana notiek vietā?
Jā, Bubble sort veic blakus esošo pāru apmaiņu, neizmantojot nekādu nozīmīgu datu struktūru. Tādējādi burbuļu kārtošanas algoritms ir iebūvēts algoritms.
Vai burbuļu kārtošanas algoritms ir stabils?
Jā, burbuļu kārtošanas algoritms ir stabils.
Kur tiek izmantots burbuļu kārtošanas algoritms?
Tā vienkāršības dēļ burbuļu kārtošana bieži tiek izmantota, lai ieviestu šķirošanas algoritma jēdzienu. Datorgrafikā tas ir populārs ar savu spēju atklāt niecīgu kļūdu (piemēram, tikai divu elementu mijmaiņu) gandrīz sakārtotos masīvos un labot to ar tikai lineāru sarežģītību (2n).
Piemērs: to izmanto daudzstūru aizpildīšanas algoritmā, kur ierobežojošās līnijas tiek sakārtotas pēc to x koordinātām noteiktā skenēšanas līnijā (līnija, kas ir paralēla x asij), un, palielinot y, mainās to secība (tiek apmainīti divi elementi). divu līniju krustojumos.
Saistītie raksti:
- Rekursīvā burbuļu kārtošana
- Kodēšanas prakse šķirošanai
- Viktorīna par burbuļu kārtošanu
- Burbuļu kārtošanas sarežģītības analīze