Пузырьковая сортировка

Сортировка пузырьком — это самый простой алгоритм сортировки, который работает путем многократной замены соседних элементов, если они находятся в неправильном порядке.

Пример:

Первый проход:

(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:

// 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 их порядок меняется (два элемента меняются местами) только на пересечениях двух линий.

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

Перевод статьи «Bubble Sort» был подготовлен дружной командой проекта Сайтостроение от А до Я.