Алгоритъм за сортиране на балончета

В този урок ще научите как работи сортирането на балончета. Също така ще намерите работещи примери за сортиране на балончета в C, C ++, Java и Python.

Bubble sort е алгоритъм, който сравнява съседните елементи и разменя техните позиции, ако не са в предвидения ред. Поръчката може да бъде възходяща или низходяща.

Как работи сортирането на балончета?

  1. Започвайки от първия индекс, сравнете първия и втория елемент. Ако първият елемент е по-голям от втория елемент, те се разменят.
    Сега сравнете втория и третия елемент. Разменете ги, ако не са в ред.
    Горният процес продължава до последния елемент. Сравнете съседните елементи
  2. Същият процес продължава и за останалите повторения. След всяка итерация най-големият елемент сред несортираните елементи се поставя в края.
    Във всяка итерация сравнението се извършва до последния несортиран елемент.
    Масивът се сортира, когато всички несортирани елементи се поставят на правилните им позиции. Сравнете съседните елементи Сравнете съседните елементи Сравнете съседните елементи

Алгоритъм за сортиране на балончета

 bubbleSort (масив) за i rightElement суап leftElement и rightElement край bubbleSort

Примери за Python, Java и 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); )

Оптимизирано сортиране на балончета

В горния код се правят всички възможни сравнения, дори ако масивът вече е сортиран. Това увеличава времето за изпълнение.

Кодът може да бъде оптимизиран чрез въвеждане на допълнителна променлива, заменена. След всяка итерация, ако тогава не се извършва размяна, няма нужда да се извършват допълнителни цикли.

В такъв случай разменената променлива е зададена като false. По този начин можем да предотвратим по-нататъшни повторения.

Алгоритъмът за оптимизирано сортиране на балончета е

 bubbleSort (масив) заменен <- false за i rightElement суап leftElement и rightElement разменен <- true end bubbleSort

Оптимизирани примери за сортиране на балончета

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

Сложност

Bubble Sort е един от най-простите алгоритми за сортиране. В алгоритъма са внедрени два цикъла.

Цикъл Брой сравнения
1-ви (n-1)
2-ри (n-2)
3-ти (n-3)
… …
последен 1

Брой сравнения: (n - 1) + (n - 2) + (n - 3) + … + 1 = n (n - 1) / 2 почти е равно на n 2

Сложност: O (n 2 )

Също така можем да анализираме сложността, като просто наблюдаваме броя на цикли. Има 2 цикъла, така че сложността еn*n = n2

Сложни времена:

  • Сложност на най-лошия случай: Ако искаме да сортираме във възходящ ред и масивът е в низходящ ред, тогава се случва най-лошият случай.O(n2)

  • Най-добрата сложност:O(n)
    Ако масивът е вече сортиран, няма нужда от сортиране.

  • Средна сложност на случая: Това се случва, когато елементите на масива са в объркан ред (нито възходящ, нито низходящ).O(n2)

Сложност на пространството: Сложността на
пространството се O(1)дължи на това, че за смяна се използва допълнителна променлива температура.

В оптимизирания алгоритъм разменената променлива добавя към сложността на пространството по този начин, което го прави O(2).

Приложения за сортиране на балончета

Bubble sort се използва в следните случаи, когато

  1. сложността на кода няма значение.
  2. предпочита се кратък код.

Интересни статии...