Метод сортировки пузырьком - шпаргалка для начинающих
Пузырьковая сортировка – один из самых простых и наглядных алгоритмов для понимания принципов работы сортировки. Несмотря на свою элементарность, она помогает освоить основы алгоритмического мышления и разобраться в базовых циклах и сравнениях.
Вы узнаете, как именно работает этот метод, где он может пригодиться и почему его не используют в сложных проектах. В статье представлены примеры кода и пояснения, которые помогут быстро освоить алгоритм на практике.
Примеры
Первый проход:
(5 1 4 2 8) (1 5 4 2 8), здесь алгоритм сравнивает два первых элемента и меняет их местами, так как (5>1).
(1 5 4 2 8) (1 4 5 2 8), меняет элементы местами, так как {displaystyle 5>4}{displaystyle 5>4}(5>4)
(1 4 5 2 8) (1 4 2 5 8), меняет элементы местами, так как {displaystyle 5>2}(5>2)
(1 4 2 5 8) (1 4 2 5 8), ввиду того, что элементы стоят на своих местах ({displaystyle 8>5}8>5), алгоритм не меняет их местами.
Второй проход:
(1 4 2 5 8) (1 4 2 5 8)
(1 4 2 5 8) (1 2 4 5 8), меняет элементы местами, так как (4>2){displaystyle 4>2}
(1 2 4 5 8) (1 2 4 5 8)
Теперь массив полностью отсортирован, но алгоритму это неизвестно. Поэтому ему необходимо осуществить полный проход и определить, что перестановок элементов не было.
Третий проход:
( 1 2 4 5 8) -> ( 1 2 4 5 8)
(1 2 4 5 8) -> (1 2 4 5 8)
(1 2 4 5 8) -> (1 2 4 5 8) )
(1 2 4 5 8 ) -> (1 2 4 5 8 )
Теперь массив отсортирован, и алгоритм может быть завершён.
Ниже в качестве примера приведена сортировка пузырьком С :
// C программа реализации пузырьковой сортировки
#include <stdio.h>
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
// функция реализации пузырьковой сортировки
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n-1; i++)
// Последние i элементы уже на месте
for (j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
}
/* Функция вывода массива на экран */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("n");
}
// Программа тестирования функций, приведенных выше
int main()
{
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array: n");
printArray(arr, n);
return 0;
}Сортировка пузырьком Java
// Java программа реализации пузырьковой сортировки
class BubbleSort
{
void bubbleSort(int arr[])
{
int n = arr.length;
for (int i = 0; i < n-1; i++)
for (int j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
{
// меняем местами temp и arr[i]
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
/* Вывод массива на экран */
void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Метод, тестирующий функции, приведенные выше
public static void main(String args[])
{
BubbleSort ob = new BubbleSort();
int arr[] = {64, 34, 25, 12, 22, 11, 90};
ob.bubbleSort(arr);
System.out.println("Sorted array");
ob.printArray(arr);
}
}Сортировка пузырьком Python
# Python реализация сортировки пузырьком
def bubbleSort(arr):
n = len(arr)
# Проход через все элементы массива
for i in range(n):
# Последние i элементы уже на месте
for j in range(0, n-i-1):
# проход массива от 0 до n-i-1
# Поменять местами, если найденный элемент больше
# чем следующий элемент
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
# Код тестирования
arr = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(arr)
print ("Сортированный массив:")
for i in range(len(arr)):
print ("%d" %arr[i]),Результат:
Сортированный массив:
11 12 22 25 34 64 90
Оптимизированная реализация
Приведенная выше сортировка методом пузырька всегда выполняется, даже если массив отсортирован. Ее можно оптимизировать путем остановки алгоритма, применяемой в том случае, если внутренний цикл не произвел никакой замены.
С/С++
// Оптимизированная реализация пузырьковой сортировки
#include <stdio.h>
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
// Оптимизированная версия пузырьковой сортировки
void bubbleSort(int arr[], int n)
{
int i, j;
bool swapped;
for (i = 0; i < n-1; i++)
{
swapped = false;
for (j = 0; j < n-i-1; j++)
{
if (arr[j] > arr[j+1])
{
swap(&arr[j], &arr[j+1]);
swapped = true;
}
}
// Если в процессе прохода не было ни одной замены, то выход из функции
if (swapped == false)
break;
}
}
/* Функция вывода массива */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("n");
}
// Программа тестирования функций, приведенных выше
int main()
{
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
printf("Сортированный массив: n");
printArray(arr, n);
return 0;
}Пузырьковая сортировка Python 3
# Оптимизированная реализация Python3
# сортировки пузырьком
# Оптимизированная версия пузырьковой сортировки
def bubbleSort(arr):
n = len(arr)
# Проход через все элементы массива
for i in range(n):
swapped = False
# Последние i элементы уже
# на месте
for j in range(0, n-i-1):
# проход через массив от 0
# n-i-1. Поменять местами элементы, если
# найденный элемент больше
# следующего
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
# Если в процессе прохода не было ни одной замены,
# то выход из функции
if swapped == False:
break
# тестирующий код
arr = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(arr)
print ("Сортированный массив :")
for i in range(len(arr)):
print ("%d" %arr[i],end=" ")Метод пузырька C - результат сортировки:
Сортированный массив:
11 12 22 25 34 64 90Худшая и средняя сложность времени: O (n * n). Наихудший случай возникает, когда массив отсортирован по обратному адресу.
Сложность наилучшего случая: O (n). Наилучший случай возникает, когда массив уже отсортирован.
Пограничные случаи: сортировка занимает минимальное время (порядок n), когда элементы уже отсортированы.
Сортировка на месте: Да.
Стабильность: Да.
В компьютерной графике пузырьковая сортировка популярна благодаря возможности обнаруживать мелкие ошибки (например, обмен всего двух элементов) в почти отсортированных массивах и исправлять ее только с линейной сложностью (2n ). Например, она используется в алгоритме заполнения полигонов, где ограничивающие линии сортируются по их координате x на определенной линии сканирования (линия, параллельная оси X ), и с увеличением Y их порядок меняется (два элемента меняются местами) только на пересечениях двух линий.
Пожалуйста, оставьте свои комментарии, если захотите поделиться дополнительной информацией про алгоритм сортировки пузырьком.
Комментарии