Алгоритм пузырьковой сортировки

В этом руководстве вы узнаете, как работает пузырьковая сортировка. Также вы найдете рабочие примеры пузырьковой сортировки в 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); )

Оптимизированная пузырьковая сортировка

В приведенном выше коде выполняются все возможные сравнения, даже если массив уже отсортирован. Это увеличивает время выполнения.

Код можно оптимизировать, добавив дополнительную переменную подкачки. После каждой итерации, если не происходит подкачки, нет необходимости выполнять дальнейшие циклы.

В таком случае для переменной swapped устанавливается значение false. Таким образом, мы можем предотвратить дальнейшие итерации.

Алгоритм оптимизированной пузырьковой сортировки:

 bubbleSort (array) swapped <- false для i rightElement swap leftElement и rightElement swapped <- 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); )

Сложность

Пузырьковая сортировка - один из простейших алгоритмов сортировки. В алгоритме реализованы два цикла.

Цикл	Количество сравнений
1-й	(п-1)
2-й	(п-2)
3-й	(п-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²)