Burbuļu šķirošanas algoritms

Šajā apmācībā jūs uzzināsiet, kā darbojas burbuļu šķirošana. Jūs atradīsit arī piemērotus burbuļu kārtošanas piemērus C, C ++, Java un Python.

Burbuļu šķirošana ir algoritms, kas salīdzina blakus esošos elementus un maina to pozīcijas, ja tie nav paredzētajā secībā. Kārtība var būt augoša vai dilstoša.

Kā darbojas burbuļu šķirošana?

Sākot ar pirmo indeksu, salīdziniet pirmo un otro elementu. Ja pirmais elements ir lielāks nekā otrais elements, tie tiek mainīti.
Tagad salīdziniet otro un trešo elementu. Mainiet tos, ja tie nav kārtībā.
Iepriekš minētais process turpinās līdz pēdējam elementam. Salīdziniet blakus esošos elementus
Tas pats process notiek arī atlikušajās atkārtojumos. Pēc katras atkārtošanas beigās tiek ievietots lielākais elements starp nešķirotajiem elementiem.
Katrā atkārtojumā salīdzinājums notiek līdz pēdējam nešķirotajam elementam.
Masīvs tiek sakārtots, kad visi nešķirotie elementi ir novietoti pareizajās pozīcijās. Salīdziniet blakus esošos elementus Salīdziniet blakus esošos elementus Salīdziniet blakus esošos elementus

Burbuļu šķirošanas algoritms

 (masīvs) i rightElement mijmaiņas pa kreisiElement un rightElement beigām bubbleSort

Python, Java un C / C ++ piemēri

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

Optimizēta burbuļu kārtošana

Iepriekš minētajā kodā tiek veikti visi iespējamie salīdzinājumi, pat ja masīvs jau ir sakārtots. Tas palielina izpildes laiku.

Kodu var optimizēt, ieviešot papildu mainīgo. Pēc katras atkārtošanas, ja pēc tam nenotiek maiņa, nav jāveic citas cilpas.

Šādā gadījumā mainīgais mainīgais tiek iestatīts kā nepatiess. Tādējādi mēs varam novērst turpmākas atkārtojumus.

Optimizēta burbuļu kārtošanas algoritms ir

 bubbleSort (masīvs) nomainīts <- false for i rightElement nomainīt pa kreisiElement un rightElement nomainīts <- true end bubbleSort

Optimizēti burbuļu šķirošanas piemēri

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

Sarežģītība

Bubble Sort ir viens no vienkāršākajiem šķirošanas algoritmiem. Algoritmā tiek ieviestas divas cilpas.

Cikls	Salīdzinājumu skaits
1	(n-1)
2	(n-2)
3	(n-3)
….	…
Pēdējais	1

Salīdzinājumu skaits: (n - 1) + (n - 2) + (n - 3) +… + 1 = n (n - 1) / 2 gandrīz vienāds ar n ²

Sarežģītība: O (n ² )

Tāpat mēs varam analizēt sarežģītību, vienkārši novērojot cilpu skaitu. Ir 2 cilpas, tāpēc sarežģītība irn*n = n²

Laika sarežģītība:

Sliktākā gadījuma sarežģītība: ja mēs vēlamies kārtot augošā secībā un masīvs ir dilstošā secībā, notiek vissliktākais gadījums.O(n²)
Labākā gadījuma sarežģītība:O(n)
ja masīvs jau ir sakārtots, tad nav nepieciešams šķirot.
Vidējā gadījuma sarežģītība: tā notiek, ja masīva elementi ir sajaukti secībā (ne augšupejoši, ne dilstoši).O(n²)