Bublinové triedenie je najjednoduchší triediaci algoritmus funguje tak, že sa priľahlé prvky opakovane vymieňajú, ak sú v nesprávnom poradí. Tento algoritmus nie je vhodný pre veľké súbory údajov, pretože jeho priemerná časová zložitosť a zložitosť najhoršieho prípadu je dosť vysoká.
Algoritmus bublinového triedenia
Odporúčaný postup Bublinové triedenie Vyskúšajte to!V algoritme bublinového triedenia
java pole zoradené
- prechádzajte zľava a porovnávajte susedné prvky a vyšší je umiestnený na pravej strane.
- Týmto spôsobom sa najväčší prvok najprv presunie na koniec úplne vpravo.
- Tento proces potom pokračuje pri hľadaní druhého najväčšieho a jeho umiestnení a tak ďalej, kým sa údaje neroztriedia.
Ako funguje bublinové triedenie?
Poďme pochopiť fungovanie bublinového triedenia pomocou nasledujúcej ilustrácie:
Vstup: arr[] = {6, 0, 3, 5}
Prvý prechod:
Najväčší prvok sa umiestni na správnu pozíciu, t. j. na koniec poľa.
Bublinový triediaci algoritmus: Umiestnenie najväčšieho prvku na správnu pozíciu
Druhý prechod:
Umiestnite druhý najväčší prvok do správnej polohy
Bublinový triediaci algoritmus: Umiestnenie druhého najväčšieho prvku na správnu pozíciu
Tretí prechod:
Umiestnite zvyšné dva prvky na ich správnu pozíciu.
Bublinový triediaci algoritmus: Umiestňovanie zostávajúcich prvkov na ich správne pozície
sčítačka plná sčítačka
- Celkový počet z prihrávok: n-1
- Celkový počet z porovnaní: n*(n-1)/2
Implementácia Bubble Sort
Nižšie je uvedená implementácia bublinového triedenia. Dá sa optimalizovať zastavením algoritmu, ak vnútorná slučka nespôsobila žiadnu výmenu.
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]); vymenené = pravda; } } // Ak neboli zamenené žiadne dva prvky // vnútornou slučkou, potom break if (swapped == false) break; } } // Funkcia na tlač poľa void printArray(int arr[], int veľkosť) { int i; pre (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]); vymenené = pravda; } } // Ak neboli žiadne dva prvky zamenené vnútornou slučkou, // potom break if (swapped == false) break; } } // Funkcia na tlač poľa void printArray(int arr[], int veľkosť) { int i; pre (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]) { // Vymeňte arr[j] a arr[j+1] temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = teplota; vymenené = pravda; } } // Ak neboli žiadne dva prvky // zamenené vnútornou slučkou, potom break if (swapped == false) break; } } // Funkcia na tlač statického poľa void printArray(int arr[], int size) { int i; pre (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] zamenené = True, ak (zamenené == False): zlomiť # Kód ovládača na otestovanie vyššie, ak __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=' ') # Tento kód upravil 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]) { // Vymeňte arr[j] a arr[j+1] temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = teplota; vymenené = pravda; } } // Ak neboli žiadne dva prvky // zamenené vnútornou slučkou, potom break if (swapped == false) break; } } // Funkcia na tlač statického poľa void printArray(int[] arr, int size) { int i; pre (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]) { // Vymeňte arr[j] a arr[j+1] temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = teplota; vymenené = pravda; } } // AK neboli žiadne dva prvky // zamenené vnútornou slučkou, potom break if (swapped == false) break; } } // Funkcia na tlač funkcie poľa printPole(pola, veľkosť) { var i; pre (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 = Pravda; } } // Ak neboli zamenené žiadne dva prvky // vnútornou slučkou, potom break if ($swapped == False) break; } } // Kód ovládača $arr = array(64, 34, 25, 12, 22, 11, 90); $len = sizeof($arr); bubbleSort($arr); echo 'Zoradené pole:
'; for($i = 0; $i< $len; $i++) echo $arr[$i].' '; // This code is contributed by ChitraNayal. ?>> Výkon
Sorted array: 11 12 22 25 34 64 90>
Analýza zložitosti bublinkového triedenia :
Časová zložitosť: O(N2)
Pomocný priestor: O(1)
Výhody bublinkového triedenia:
- Bublinové triedenie je jednoduché na pochopenie a implementáciu.
- Nevyžaduje žiadny ďalší pamäťový priestor.
- Ide o stabilný triediaci algoritmus, čo znamená, že prvky s rovnakou hodnotou kľúča si zachovávajú svoje relatívne poradie v triedenom výstupe.
Nevýhody bublinkového triedenia:
- Bublinové triedenie má časovú zložitosť O(N2), vďaka čomu je pri veľkých súboroch údajov veľmi pomalý.
- Bublinové triedenie je algoritmus triedenia založený na porovnaní, čo znamená, že na určenie relatívneho poradia prvkov vo vstupnej množine údajov vyžaduje operátor porovnávania. V určitých prípadoch môže obmedziť účinnosť algoritmu.
Niektoré časté otázky súvisiace s bublinovým triedením:
Aký je Boundary Case pre Bubble sort?
Bublinové triedenie trvá minimálny čas (poradie n), keď sú prvky už zoradené. Preto je najlepšie vopred skontrolovať, či je pole už zoradené alebo nie, aby ste sa vyhli O(N2) časová zložitosť.
Prebieha triedenie v bublinovom triedení?
Áno, Bubble sort vykonáva výmenu susedných párov bez použitia akejkoľvek významnej dátovej štruktúry. Algoritmus Bubble sort je teda algoritmus na mieste.
Je algoritmus Bubble sort stabilný?
Áno, algoritmus triedenia bublín je stabilný.
Kde sa používa algoritmus Bubble sort?
Bublinové triedenie sa kvôli svojej jednoduchosti často používa na zavedenie konceptu triediaceho algoritmu. V počítačovej grafike je populárny pre svoju schopnosť odhaliť malú chybu (ako zámena iba dvoch prvkov) v takmer zoradených poliach a opraviť ju len s lineárnou zložitosťou (2n).
Príklad: Používa sa v algoritme vypĺňania polygónov, kde sú ohraničujúce čiary zoradené podľa ich súradnice x na špecifickej čiare skenovania (čiara rovnobežná s osou x) a so zvyšujúcim sa y sa mení iba ich poradie (dva prvky sú zamenené). na priesečníkoch dvoch čiar.
Súvisiace články:
- Rekurzívne bublinové triedenie
- Cvičenie kódovania pri triedení
- Kvíz o bublinovom triedení
- Analýza zložitosti bublinkového triedenia