Участник:Alexeyshekhanov/Сортировка пузырьком: различия между версиями

Версия 18:33, 8 ноября 2023

Сортировка пузырьком

Содержание

1 Свойства и структура алгоритма
2 Программная реализация алгоритма
3 Литература

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Сортировка пузырьком — это алгоритм сортировки, который последовательно проходит по списку, сравнивает пары соседних элементов и меняет их местами, если они стоят в неправильном порядке. Этот процесс продолжается до тех пор, пока весь список не будет отсортирован. Название "пузырьком" происходит от того, что наибольшие элементы "всплывают" к концу списка, как пузырьки воды во время вспенивания.

1.2 Математическое описание алгоритма

Давайте представим список из n элементов, обозначим его как A[0], A[1], ..., A[n-1]. Сортировка пузырьком выполняет следующие шаги:

• Начнем с индекса i = 0.
• Для каждого i от 0 до n-1, сравниваем A[i] и A[i+1]. Если A[i] > A[i+1], меняем их местами.
• После первого прохода самый большой элемент окажется в конце списка.
• Уменьшаем n на 1 и повторяем шаги 1 и 2 для оставшихся элементов.
• Продолжаем выполнять проходы до тех пор, пока список не станет отсортированным.

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

1.9 Входные и выходные данные алгоритма

Входные данные: Произвольный массив размера n
Выходные данные: Тот же самый массив, но уже отсортированный

1.10 Свойства алгоритма

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература

Левитин А. В. Глава 3. Метод грубой силы: Пузырьковая сортировка // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 144—146. — 576 с. — ISBN 978-5-8459-0987-9
Абрамов С. А., Лекции о сложности алгоритмов. — М.: МЦНМО, 2009. - 256 с. - ISBN 978-5-94057-433-0

@@ Строка 17: / Строка 17: @@
 ===Ресурс параллелизма алгоритма===
 ===Входные и выходные данные алгоритма===
+'''Входные данные:''' Произвольный массив размера n<br>
+'''Выходные данные:''' Тот же самый массив, но уже отсортированный
 ===Свойства алгоритма===
 ==Программная реализация алгоритма==