Algoritem razvrščanja mehurčkov

V tej vadnici boste izvedeli, kako deluje razvrščanje mehurčkov. Prav tako boste našli delovne primere mehurčkov v C, C ++, Java in Python.

Bubble sort je algoritem, ki primerja sosednje elemente in zamenja njihove položaje, če niso v predvidenem vrstnem redu. Vrstni red je lahko naraščajoč ali padajoč.

Kako deluje razvrščanje mehurčkov?

Od prvega indeksa primerjajte prvi in drugi element.Če je prvi element večji od drugega, se zamenjata.
Zdaj primerjajte drugi in tretji element. Zamenjajte jih, če niso v redu.
Zgornji postopek se nadaljuje do zadnjega elementa. Primerjajte sosednje elemente
Enak postopek se nadaljuje pri preostalih ponovitvah. Po vsaki ponovitvi se na koncu postavi največji element med nesortiranimi elementi.
V vsaki ponovitvi poteka primerjava do zadnjega nerazvrščenega elementa.
Polje je razvrščeno, ko so vsi nesortirani elementi postavljeni na svoje pravilne položaje. Primerjaj sosednje elemente Primerjaj sosednje elemente Primerjaj sosednje elemente

Algoritem razvrščanja mehurčkov

 bubbleSort (matrika) za i rightElement swap leftElement in rightElement end bubbleSort

Primeri Python, Java in 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); )

Optimizirano razvrščanje mehurčkov

V zgornji kodi so narejene vse možne primerjave, tudi če je polje že razvrščeno. Poveča čas izvedbe.

Kodo lahko optimizirate z uvedbo zamenjane spremenljivke. Če po vsaki ponovitvi ni zamenjave, ni treba izvajati nadaljnjih zank.

V takem primeru je spremenljivka zamenjana nastavljena na false. Tako lahko preprečimo nadaljnje ponovitve.

Algoritem za optimizirano razvrščanje mehurčkov je

 bubbleSort (matrika) zamenjana <- false za i rightElement zamenjava leftElement in rightElement zamenjana <- true end bubbleSort

Primeri optimiziranega razvrščanja po mehurčkih

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

Kompleksnost

Razvrstitev po mehurčkih je eden najpreprostejših algoritmov za razvrščanje. V algoritmu sta izvedeni dve zanki.

Cikel	Število primerjav
1.	(n-1)
2.	(n-2)
3.	(n-3)
…	…
zadnji	1.

Število primerjav: (n - 1) + (n - 2) + (n - 3) + … + 1 = n (n - 1) / 2 skoraj enako n ²

Kompleksnost: O (n ² )

Zapletenost lahko analiziramo tudi tako, da preprosto opazujemo število zank. Obstajata 2 zanki, zato je zapletenostn*n = n²

Časovne zapletenosti:

Najslabša zapletenost: če želimo razvrstiti v naraščajočem vrstnem redu in je matrika v padajočem vrstnem redu, se zgodi najslabši primer.O(n²)
Najboljša zapletenost:O(n)
Če je polje že razvrščeno, razvrščanje ni potrebno.
Povprečna zapletenost primerov: Pojavi se, če so elementi matrike v vrstnem redu (niti naraščajoče niti padajoče).O(n²)