Tässä opetusohjelmassa opit, miten kuplalajittelu toimii. Lisäksi löydät toimivia esimerkkejä kuplalajittelusta C-, C ++ -, Java- ja Python-versioissa.
Bubble sort on algoritmi, joka vertaa vierekkäisiä elementtejä ja vaihtaa niiden sijainnit, jos ne eivät ole aiotussa järjestyksessä. Järjestys voi olla nouseva tai laskeva.
Kuinka Bubble Sort toimii?
- Vertaa ensimmäisestä indeksistä alkaen ensimmäistä ja toista elementtiä. Jos ensimmäinen elementti on suurempi kuin toinen, ne vaihdetaan.
Vertaa nyt toista ja kolmatta elementtiä. Vaihda ne, jos ne eivät ole kunnossa.
Edellä mainittu prosessi jatkuu viimeiseen elementtiin asti.
Vertaa vierekkäisiä elementtejä - Sama prosessi jatkuu muilla iteraatioilla. Jokaisen iteraation jälkeen suurin osa lajittelemattomien elementtien joukosta sijoitetaan loppuun.
Kussakin iteraatiossa vertailu tapahtuu viimeiseen lajittelemattomaan elementtiin asti.
Matriisi lajitellaan, kun kaikki lajittelemattomat elementit asetetaan oikeisiin paikkoihin.
Vertaa vierekkäisiä elementtejä 
Vertaa vierekkäisiä elementtejä 
Vertaa vierekkäisiä elementtejä
Kuplalajittelualgoritmi
bubbleSort (taulukko) i rightElementille Vaihda leftElement ja rightElement loppuun bubbleSort
Python-, Java- ja C / C ++ -esimerkkejä
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); )
Optimoitu kuplalajittelu
Yllä olevassa koodissa tehdään kaikki mahdolliset vertailut, vaikka taulukko on jo lajiteltu. Se pidentää suoritusaikaa.
Koodi voidaan optimoida ottamalla käyttöön ylimääräinen muuttuja. Jokaisen iteroinnin jälkeen, jos silloin ei tapahdu vaihtamista, ei ole tarvetta suorittaa muita silmukoita.
Tällöin vaihdettu muuttuja asetetaan vääräksi. Siten voimme estää uudet toistot.
Optimoitu kuplalajittelun algoritmi on
bubbleSort (matriisi) vaihdettu <- false for i rightElement vaihda vasemmalleElement ja rightElement vaihdettu <- true end bubbleSort
Optimoituja kuplalajitteluesimerkkejä
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); )
Monimutkaisuus
Bubble Sort on yksi yksinkertaisimmista lajittelualgoritmeista. Algoritmissa on kaksi silmukkaa.
| Sykli | Vertailujen määrä |
|---|---|
| 1 | (n-1) |
| 2. | (n-2) |
| 3. | (n-3) |
| …. | … |
| kestää | 1 |
Vertailujen lukumäärä: (n - 1) + (n - 2) + (n - 3) +… + 1 = n (n - 1) / 2 on lähes yhtä suuri kuin n 2
Monimutkaisuus: O (n 2 )
Voimme myös analysoida monimutkaisuutta yksinkertaisesti tarkkailemalla silmukoiden määrää. Silmukoita on 2, joten monimutkaisuus onn*n = n2
Ajan monimutkaisuus:
-
Pahimman tapauksen monimutkaisuus: Jos haluamme lajitella nousevassa järjestyksessä ja taulukko on laskevassa järjestyksessä, tapahtuu pahin tapaus.
O(n2) -
Parhaan tapauksen monimutkaisuus:
O(n)
Jos taulukko on jo lajiteltu, lajittelua ei tarvita. -
Keskimääräinen tapauksen monimutkaisuus: Se tapahtuu, kun matriisin elementit ovat sekaisin (ei nousevia eikä laskevia).
O(n2)
Avaruuden monimutkaisuus:
Avaruuden monimutkaisuus johtuu O(1)siitä, että vaihtamiseen käytetään ylimääräistä muuttuvaa lämpötilaa.
Optimoidussa algoritmissa vaihdettu muuttuja lisää tilaa monimutkaisuuteen, mikä tekee siitä O(2).
Bubble Sort -sovellukset
Kuplalajittelua käytetään seuraavissa tapauksissa, joissa
- koodin monimutkaisuudella ei ole merkitystä.
- lyhyt koodi on suositeltava.
