Algoritmus třídění bublin

V tomto kurzu se naučíte, jak funguje třídění bublin. Pracovní příklady třídění bublin najdete také v jazycích C, C ++, Java a Python.

Třídění bublin je algoritmus, který porovnává sousední prvky a zaměňuje jejich polohy, pokud nejsou v zamýšleném pořadí. Pořadí může být vzestupné nebo sestupné.

Jak Bubble Sort funguje?

Počínaje prvním indexem porovnejte první a druhý prvek. Pokud je první prvek větší než druhý prvek, vymění se.
Nyní porovnejte druhý a třetí prvek. Pokud nejsou v pořádku, vyměňte je.
Výše uvedený proces pokračuje až do posledního prvku. Porovnejte sousední prvky
Stejný proces pokračuje pro zbývající iterace. Po každé iteraci je největší prvek mezi netříděnými prvky umístěn na konec.
V každé iteraci probíhá srovnání až do posledního netříděného prvku.
Pole je tříděno, když jsou všechny netříděné prvky umístěny na správných pozicích. Porovnejte sousední prvky Porovnejte sousední prvky Porovnejte sousední prvky

Algoritmus třídění bublin

 bubbleSort (pole) pro i rightElement zaměnit leftElement a rightElement end bubbleSort

Python, Java a C / C ++ příklady

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é třídění bublin

Ve výše uvedeném kódu jsou provedena všechna možná srovnání, i když je pole již tříděno. Zvyšuje dobu provádění.

Kód lze optimalizovat zavedením extra proměnné zaměněné. Po každé iteraci, pokud nedochází k žádnému swapování, není nutné provádět další smyčky.

V takovém případě je proměnná zaměněna nastavena na hodnotu false. Můžeme tedy zabránit dalším iteracím.

Algoritmus pro optimalizované třídění bublin je

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

Příklady optimalizovaného třídění bublin

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

Složitost

Bubble Sort je jedním z nejjednodušších třídicích algoritmů. V algoritmu jsou implementovány dvě smyčky.

Cyklus	Počet srovnání
1. místo	(n-1)
2. místo	(n-2)
3. místo	(n-3)
….	…
poslední	1

Počet srovnání: (n - 1) + (n - 2) + (n - 3) +… + 1 = n (n - 1) / 2 téměř odpovídá n ²

Složitost: O (n ² )

Můžeme také analyzovat složitost pouhým sledováním počtu smyček. K dispozici jsou 2 smyčky, takže složitost jen*n = n²

Časová složitost:

Složitost nejhoršího případu: Pokud chceme třídit vzestupně a pole je v sestupném pořadí, nastane nejhorší případ.O(n²)
Nejlepší případová složitost:O(n)
Pokud je pole již tříděno, není třeba jej třídit.
Průměrná složitost případu: Dochází k němu, když jsou prvky pole v neuspořádaném pořadí (ani vzestupně, ani sestupně).O(n²)