Šioje pamokoje sužinosite, kaip veikia burbulų rūšiavimas. Taip pat rasite veikiančių burbulų rūšiavimo pavyzdžių C, C ++, Java ir Python.
„Bubble sort“ yra algoritmas, lyginantis gretimus elementus ir pakeičiantis jų pozicijas, jei jie nėra numatyta tvarka. Tvarka gali būti didėjanti arba mažėjanti.
Kaip veikia burbulų rūšiavimas?
- Pradėdami nuo pirmojo indekso, palyginkite pirmąjį ir antrąjį elementus. Jei pirmasis elementas yra didesnis nei antrasis, jie keičiami.
Dabar palyginkite antrąjį ir trečiąjį elementus. Pakeiskite juos, jei jie nėra tvarkingi.
Minėtas procesas tęsiasi iki paskutinio elemento.
Palyginkite gretimus elementus - Tas pats procesas vyksta ir likusių kartojimų atveju. Po kiekvienos iteracijos pabaigoje dedamas didžiausias elementas tarp nerūšiuotų elementų.
Kiekvienoje iteracijoje palyginimas atliekamas iki paskutinio nerūšiuoto elemento.
Masyvas yra rūšiuojamas, kai visi nerūšiuoti elementai yra išdėstyti teisingose vietose.
Palyginkite gretimus elementus 
Palyginkite gretimus elementus 
Palyginkite gretimus elementus
Burbulų rūšiavimo algoritmas
„bubbleSort“ (masyvas) i rightElement pakeiskite kairęElement ir rightElement pabaigos bubbleSort
„Python“, „Java“ ir „C / C ++“ pavyzdžiai
„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); )
Optimizuotas burbulų rūšiavimas
Ankstesniame kode visi galimi palyginimai atliekami, net jei masyvas jau yra rūšiuojamas. Tai padidina vykdymo laiką.
Kodas gali būti optimizuotas įvedus papildomą kintamąjį. Po kiekvieno pakartojimo, jei tada nėra keitimo, nebereikia atlikti tolesnių kilpų.
Tokiu atveju kintamasis keičiamas yra nustatytas klaidingas. Taigi galime išvengti tolesnių pakartojimų.
Optimizuoto burbulų rūšiavimo algoritmas yra
bubbleSort (masyvas) pakeistas <- false už i rightElement sukeisti kairęElement ir rightElement pakeistas <- true end bubbleSort
Optimizuoti burbulų rūšiavimo pavyzdžiai
„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); )
Sudėtingumas
„Bubble Sort“ yra vienas paprasčiausių rūšiavimo algoritmų. Algoritme įgyvendinamos dvi kilpos.
| Ciklas | Palyginimų skaičius |
|---|---|
| 1-oji | (n-1) |
| 2-oji | (n-2) |
| 3 d | (n-3) |
| …. | … |
| paskutinis | 1 |
Palyginimų skaičius: (n - 1) + (n - 2) + (n - 3) +… + 1 = n (n - 1) / 2 beveik lygus n 2
Sudėtingumas: O (n 2 )
Be to, mes galime analizuoti sudėtingumą, tiesiog stebėdami kilpų skaičių. Yra 2 kilpos, taigi sudėtingumas yran*n = n2
Laiko sudėtingumas:
-
Blogiausio atvejo sudėtingumas: Jei norime rūšiuoti didėjimo tvarka ir masyvas yra mažėjimo tvarka, įvyksta blogiausias atvejis.
O(n2) -
Geriausio atvejo sudėtingumas:
O(n)
jei masyvas jau yra rūšiuojamas, tada rūšiuoti nereikia. -
Vidutinis atvejo sudėtingumas: Tai įvyksta, kai masyvo elementai yra susimaišę (nei didėjant, nei mažėjant).
O(n2)
Erdvės sudėtingumas:
Erdvės sudėtingumas yra O(1)todėl, kad keičiamasi papildomai kintama temperatūra.
Optimizuotame algoritme pakeistas kintamasis padidina erdvės sudėtingumą, todėl tai daro O(2).
Burbulų rūšiavimo programos
Burbulų rūšiavimas naudojamas šiais atvejais:
- kodo sudėtingumas neturi reikšmės.
- pirmenybė teikiama trumpam kodui.
