Algoritmus triedenia bublín

V tomto výučbe sa dozviete, ako funguje triedenie bublín. Pracovné príklady triedenia bublín nájdete aj v jazykoch C, C ++, Java a Python.

Bublinové triedenie je algoritmus, ktorý porovnáva susedné prvky a zamieňa ich polohy, ak nie sú v zamýšľanom poradí. Poradie môže byť vzostupné alebo zostupné.

Ako funguje triedenie bublín?

Počnúc prvým indexom porovnajte prvý a druhý prvok. Ak je prvý prvok väčší ako druhý prvok, dôjde k ich zámene.
Teraz porovnajte druhý a tretí prvok. Ak nie sú v poriadku, vymeňte ich.
Vyššie uvedený proces pokračuje až do posledného prvku. Porovnajte susedné prvky
Rovnaký proces pokračuje aj pri zostávajúcich iteráciách. Po každej iterácii sa najväčší prvok spomedzi netriedených prvkov umiestni na koniec.
V každej iterácii sa porovnanie uskutoční až po posledný netriedený prvok.
Pole je zoradené, keď sú všetky netriedené prvky umiestnené na správnych pozíciách. Porovnajte susedné prvky Porovnajte susedné prvky Porovnajte susedné prvky

Algoritmus triedenia bublín

 bubbleSort (pole) pre i rightElement zameniť leftElement a rightElement koniec bubbleSort

Príklady jazyka Python, Java a C / C ++

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

Optimalizované triedenie bublín

Vo vyššie uvedenom kóde sú vykonané všetky možné porovnania, aj keď je pole už zoradené. Zvyšuje čas vykonania.

Kód je možné optimalizovať zavedením extra premennej. Ak po každej iterácii nedochádza k zámene, nie je potrebné vykonávať ďalšie slučky.

V takom prípade je premenná vymenená nastavená na hodnotu False. Môžeme tak zabrániť ďalším iteráciám.

Algoritmus pre optimalizované triedenie bublín je

 bubbleSort (array) swapped <- false for i rightElement swapped leftElement and rightElement swapped <- true end bubbleSort

Príklady optimalizovaného triedenia bublín

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

Zložitosť

Bubble Sort je jeden z najjednoduchších algoritmov triedenia. V algoritme sú implementované dve slučky.

Cyklus	Počet porovnaní
1	(n-1)
2	(n-2)
3	(n-3)
….	…
posledný	1

Počet porovnaní: (n - 1) + (n - 2) + (n - 3) + … + 1 = n (n - 1) / 2 sa takmer rovná n ²

Zložitosť: O (n ² )

Tiež môžeme analyzovať zložitosť jednoduchým sledovaním počtu slučiek. K dispozícii sú 2 slučky, takže zložitosť jen*n = n²

Časová zložitosť:

Najhoršia zložitosť: Ak chceme triediť vzostupne a pole je v zostupnom poradí, nastane najhorší prípad.O(n²)
Zložitosť najlepších prípadov:O(n)
Ak je pole už zoradené, nie je potrebné ho triediť.
Priemerná zložitosť prípadu: Vyskytuje sa, keď sú prvky poľa v neusporiadanom poradí (ani vzostupne, ani zostupne).O(n²)