Алгоритм сортування міхурів

У цьому уроці ви дізнаєтесь, як працює сортування бульбашок. Крім того, ви знайдете робочі приклади сортування міхурів у C, C ++, Java та Python.

Сортування за міхурами - це алгоритм, який порівнює сусідні елементи та міняє місцями їх місця, якщо вони не відповідають призначеному порядку. Порядок може бути зростаючим або низхідним.

Як працює сортування міхурів?

Починаючи з першого індексу, порівняйте перший і другий елементи. Якщо перший елемент більше, ніж другий елемент, вони поміняються місцями.
А тепер порівняйте другий і третій елементи. Поміняйте місцями, якщо вони не в порядку.
Вищевказаний процес триває до останнього елемента. Порівняйте сусідні елементи
Той самий процес продовжується для решти ітерацій. Після кожної ітерації в кінці розміщується найбільший елемент серед несортованих елементів.
У кожній ітерації порівняння відбувається до останнього невідсортованого елемента.
Масив сортується, коли всі невідсортовані елементи розміщуються у своїх правильних положеннях. Порівняйте сусідні елементи Порівняйте сусідні елементи Порівняйте сусідні елементи

Алгоритм сортування міхурів

 bubbleSort (масив) для i rightElement поміняти місцями leftElement і rightElement end 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 ²

Складність: O (n ² )

Крім того, ми можемо проаналізувати складність, просто спостерігаючи за кількістю петель. Є 2 петлі, тож складністьn*n = n²

Складність часу:

Найгірша складність: якщо ми хочемо сортувати за зростанням, а масив - за спаданням, тоді трапляється найгірший випадок.O(n²)
Складність найкращого випадку:O(n)
якщо масив вже відсортовано, сортування не потрібно.
Середня складність справи: Це відбувається, коли елементи масиву розташовані в порядку перемішування (ні за зростанням, ні за спаданням).O(n²)