Selles õpetuses saate teada, kuidas mullide sortimine töötab. Samuti leiate mullide sortimise toimivaid näiteid C, C ++, Java ja Python.
Mullide sortimine on algoritm, mis võrdleb külgnevaid elemente ja vahetab nende positsioone, kui need pole ettenähtud järjekorras. Järjekord võib olla kasvav või kahanev.
Kuidas mullide sorteerimine töötab?
- Alustades esimesest indeksist, võrrelge esimest ja teist elementi. Kui esimene element on suurem kui teine, siis need vahetatakse.
Nüüd võrrelge teist ja kolmandat elementi. Vahetage need, kui need pole korras.
Ülaltoodud protsess kestab kuni viimase elemendini.
Võrrelge külgnevaid elemente - Sama protsess toimub ka ülejäänud korduste puhul. Pärast iga iteratsiooni pannakse kõige suurem sortimata elementide hulgast element.
Igas iteratsioonis toimub võrdlus kuni viimase sorteerimata elemendini.
Massiiv sorteeritakse siis, kui kõik sorteerimata elemendid on paigutatud õigesse asendisse.
Võrrelge külgnevaid elemente 
Võrrelge külgnevaid elemente 
Võrrelge külgnevaid elemente
Mullide sorteerimise algoritm
bubbleSort (massiiv) i rightElement jaoks vahetage vasakElement ja rightElement lõpeb bubbleSort
Pythoni, Java ja C / C ++ näited
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); )
Optimeeritud mullide sorteerimine
Ülaltoodud koodis tehakse kõik võimalikud võrdlused isegi siis, kui massiiv on juba sorteeritud. See pikendab täitmisaega.
Koodi saab optimeerida lisamuutuja sisseviimisega. Pärast iga kordamist, kui vahetamist ei toimu, pole vaja täiendavaid tsükleid läbi viia.
Sellisel juhul on muutuja vahetatud väärtuseks vale. Seega saame vältida edasisi kordusi.
Optimeeritud mullide sorteerimise algoritm on
bubbleSort (massiiv) vahetatud <- false for i rightElement vahetada vasakulElement ja rightElement vahetatud <- true end bubbleSort
Optimeeritud mullide sorteerimise näited
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); )
Keerukus
Mullisorteerimine on üks lihtsamaid sorteerimisalgoritme. Algoritmis on rakendatud kaks tsüklit.
| Tsükkel | Võrdluste arv |
|---|---|
| 1. | (n-1) |
| 2 | (n-2) |
| 3 | (n-3) |
| …. | … |
| viimane | 1 |
Võrdluste arv: (n - 1) + (n - 2) + (n - 3) +… + 1 = n (n - 1) / 2 on peaaegu võrdne n 2
Keerukus: O (n 2 )
Samuti võime analüüsida keerukust, lihtsalt jälgides silmuste arvu. Seal on 2 silmust, nii et keerukus onn*n = n2
Aja keerukus:
-
Halvima juhtumi keerukus: kui tahame sortida kasvavas järjekorras ja massiiv on kahanevas järjekorras, siis juhtub halvim juhtum.
O(n2) -
Parima juhtumi keerukus:
O(n)
kui massiiv on juba sorteeritud, pole sortimiseks vaja. -
Keskmine juhtumite keerukus: see juhtub siis, kui massiivi elemendid on segamini (ei tõusvas ega kahanevas).
O(n2)
Ruumi keerukus:
Ruumi keerukus tuleneb O(1)sellest, et vahetamiseks kasutatakse täiendavat muutuvat temperatuuri.
Optimeeritud algoritmis suurendab vahetatav muutuja ruumi keerukust, muutes selle O(2).
Mullide sortimisrakendused
Mullisorte kasutatakse järgmistel juhtudel, kui
- koodi keerukus pole oluline.
- eelistatakse lühikoodi.
