Введение в алгоритм пузырьковой сортировки

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

В этой статье вы узнаете о работе алгоритма пузырьковой сортировки, псевдокода пузырьковой сортировки. алгоритм, его временная и пространственная сложность и его реализация на различных языках программирования, таких как C ++, Python, C и JavaScript.

Как работает алгоритм пузырьковой сортировки?

Пузырьковая сортировка - это простейший алгоритм сортировки, который многократно проходит по списку, сравнивает соседние элементы и меняет их местами, если они расположены в неправильном порядке. Более эффективно эту концепцию можно пояснить на примере. Рассмотрим несортированный массив со следующими элементами: {16, 12, 15, 13, 19}.

Пример:

Здесь сравниваются соседние элементы, и, если они не в порядке возрастания, они меняются местами.

Псевдокод алгоритма пузырьковой сортировки

В псевдокоде, алгоритм пузырьковой сортировки можно выразить как:

bubbleSort (Arr [], размер)
// цикл для доступа к каждому элементу массива
для i = 0 до size-1 выполните:
// цикл для сравнения элементов массива
для j = 0 до size-i-1 выполните:
// сравниваем соседние элементы
если Arr [j]> Arr [j + 1], то
// меняем их местами
своп (Arr [j], Arr [j + 1])
конец, если
конец для
конец для
конец

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

Таким образом, псевдокод оптимизированного алгоритма пузырьковой сортировки можно выразить как:

bubbleSort (Arr [], размер)
// цикл для доступа к каждому элементу массива
для i = 0 до size-1 выполните:
// проверяем, происходит ли подкачка
swapped = false
// цикл для сравнения элементов массива
для j = 0 до size-i-1 выполните:
// сравниваем соседние элементы
если Arr [j]> Arr [j + 1], то
// меняем их местами
своп (Arr [j], Arr [j + 1])
swapped = true
конец, если
конец для
// если никакие элементы не были заменены местами, это означает, что массив сейчас отсортирован, а затем прервать цикл.
если (не поменял местами) то
перерыв
конец, если
конец для
конец

Временная сложность и вспомогательное пространство алгоритма пузырьковой сортировки

Наихудшая временная сложность алгоритма пузырьковой сортировки составляет O (n ^ 2). Это происходит, когда массив находится в порядке убывания, и вы хотите отсортировать его в порядке возрастания или наоборот.

Оптимальная временная сложность алгоритма пузырьковой сортировки составляет O (n). Это происходит, когда массив уже отсортирован.

Связанный: Что такое нотация Big-O?

Средняя временная сложность алгоритма пузырьковой сортировки составляет O (n ^ 2). Это происходит, когда элементы массива находятся в беспорядочном порядке.

Вспомогательное пространство, необходимое для алгоритма пузырьковой сортировки, составляет O (1).

Реализация алгоритма пузырьковой сортировки на C ++

Ниже представлена ​​реализация алгоритма пузырьковой сортировки на C ++:

// C ++ реализация
// оптимизированный алгоритм пузырьковой сортировки
#включать 
используя пространство имен std;
// Функция для выполнения пузырьковой сортировки
void bubbleSort (int arr [], int size) {
// Цикл для доступа к каждому элементу массива
для (int i = 0; я // Переменная для проверки, происходит ли подкачка
bool swapped = false;
// цикл для сравнения двух соседних элементов массива
для (int j = 0; j // Сравнение двух соседних элементов массива
if (arr [j]> arr [j + 1]) {
// Меняем местами оба элемента, если они
// не в правильном порядке
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = темп;
swapped = true;
}
}
// Если никакие элементы не поменялись местами, значит, массив сейчас отсортирован,
// затем прервать цикл.
if (поменяно местами == false) {
перерыв;
}
}
}
// Печатает элементы массива
void printArray (int arr [], int size) {
для (int i = 0; я cout << arr [i] << "";
}
cout << endl;
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// Находим длину массива
int size = sizeof (arr) / sizeof (arr [0]);
// Печать заданного несортированного массива
cout << "Несортированный массив:" << endl;
printArray (обр., размер);
// Вызов функции bubbleSort ()
bubbleSort (обр., размер);
// Печать отсортированного массива
cout << "Отсортированный массив в возрастающем порядке:" << endl;
printArray (обр., размер);
возврат 0;
}

Выход:

Несортированный массив: 
16 12 15 13 19 
Отсортированный массив в возрастающем порядке:
12 13 15 16 19

Реализация алгоритма пузырьковой сортировки на Python

Ниже представлена ​​реализация алгоритма пузырьковой сортировки на Python:

# Реализация Python
# оптимизированный алгоритм пузырьковой сортировки
# Функция для выполнения пузырьковой сортировки
def bubbleSort (обр., размер):
# Цикл для доступа к каждому элементу списка
для i в диапазоне (размер-1):
# Переменная, чтобы проверить, происходит ли подкачка
swapped = Ложь
# цикл для сравнения двух соседних элементов списка
для j в диапазоне (размер-i-1):
# Сравнение двух соседних элементов списка
если arr [j]> arr [j + 1]:
temp = arr [j]
arr [j] = arr [j + 1]
arr [j + 1] = темп
swapped = True
# Если никакие элементы не поменялись местами, это означает, что список отсортирован,
# затем разорвать цикл.
если поменять местами == False:
перерыв
# Печатает элементы списка
def printArray (arr):
для элемента в arr:
печать (элемент, конец = "")
Распечатать("")
arr = [16, 12, 15, 13, 19]
# Определение длины списка
размер = длина (об)
# Печать заданного несортированного списка
print ("Несортированный список:")
printArray (обр)
# Вызов функции bubbleSort ()
bubbleSort (обр., размер)
# Печать отсортированного списка
print ("Отсортированный список в возрастающем порядке:")
printArray (обр)

Выход:

Несортированный список:
16 12 15 13 19 
Отсортированный список в порядке возрастания:
12 13 15 16 19

Связанный: Как использовать циклы For в Python

C Реализация алгоритма пузырьковой сортировки

Ниже представлена ​​реализация алгоритма пузырьковой сортировки на языке C:

// C реализация
// оптимизированный алгоритм пузырьковой сортировки
#включать 
#включать 
// Функция для выполнения пузырьковой сортировки
void bubbleSort (int arr [], int size) {
// Цикл для доступа к каждому элементу массива
для (int i = 0; я // Переменная для проверки, происходит ли подкачка
bool swapped = false;
// цикл для сравнения двух соседних элементов массива
для (int j = 0; j // Сравнение двух соседних элементов массива
if (arr [j]> arr [j + 1]) {
// Меняем местами оба элемента, если они
// не в правильном порядке
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = темп;
swapped = true;
}
}
// Если никакие элементы не поменялись местами, значит, массив сейчас отсортирован,
// затем прервать цикл.
if (поменяно местами == false) {
перерыв;
}
}
}
// Печатает элементы массива
void printArray (int arr [], int size) {
для (int i = 0; я printf ("% d", arr [i]);
}
printf ("\ ⁠n");
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// Находим длину массива
int size = sizeof (arr) / sizeof (arr [0]);
// Печать заданного несортированного массива
printf ("Несортированный массив: \ ⁠n");
printArray (обр., размер);
// Вызов функции bubbleSort ()
bubbleSort (обр., размер);
// Печать отсортированного массива
printf ("Отсортированный массив в возрастающем порядке: \ ⁠n");
printArray (обр., размер);
возврат 0;
}

Выход:

Несортированный массив: 
16 12 15 13 19 
Отсортированный массив в возрастающем порядке: 
12 13 15 16 19

Реализация алгоритма пузырьковой сортировки в JavaScript

Ниже представлена ​​реализация алгоритма пузырьковой сортировки в JavaScript:

// JavaScript-реализация
// оптимизированный алгоритм пузырьковой сортировки
// Функция для выполнения пузырьковой сортировки
function bubbleSort (arr, size) {
// Цикл для доступа к каждому элементу массива
для (пусть i = 0; я// Переменная для проверки, происходит ли подкачка
var swapped = false;
// цикл для сравнения двух соседних элементов массива
для (пусть j = 0; j// Сравнение двух соседних элементов массива
if (arr [j]> arr [j + 1]) {
// Меняем местами оба элемента, если они
// не в правильном порядке
пусть temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = темп;
swapped = true;
}
// Если никакие элементы не поменялись местами, значит, массив сейчас отсортирован,
// затем прервать цикл.
if (поменяно местами == false) {
перерыв;
}
}
}
}
// Печатает элементы массива
function printArray (arr, size) {
для (пусть i = 0; яdocument.write (arr [i] + "");
}
document.write ("
")
}
var arr = [16, 12, 15, 13, 19];
// Находим длину массива
var size = arr.length;
// Печать заданного несортированного массива
document.write ("Несортированный массив: 
");
printArray (обр., размер);
// Вызов функции bubbleSort ()
bubbleSort (обр., размер);
// Печать отсортированного массива
document.write ("Отсортированный массив в возрастающем порядке: 
");
printArray (обр., размер);

Выход:

Несортированный массив:
16 12 15 13 19
Отсортированный массив в возрастающем порядке:
12 15 13 16 19

Теперь вы понимаете работу алгоритма пузырьковой сортировки

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

Используя Python, вы можете легко реализовать алгоритм пузырьковой сортировки. Если вы не знакомы с Python и хотите начать свое путешествие, отличный выбор - начать со сценария «Hello World».

Как начать работу с Python с помощью скрипта «Hello World»

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

Читать далее

Об авторе