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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 11: Строка 11:
 
  • Уменьшаем n на 1 и повторяем шаги 1 и 2 для оставшихся элементов.
 
  • Уменьшаем n на 1 и повторяем шаги 1 и 2 для оставшихся элементов.
 
  • Продолжаем выполнять проходы до тех пор, пока список не станет отсортированным.
 
  • Продолжаем выполнять проходы до тех пор, пока список не станет отсортированным.
 +
 
===Вычислительное ядро алгоритма===
 
===Вычислительное ядро алгоритма===
 +
Вычислительное ядро последовательной версии сортировки пузырьком можно составить из, в худшем случае, <math>\frac{n (n - 1)}{2}</math> сравнений и обменов.
 +
 
===Макроструктура алгоритма===
 
===Макроструктура алгоритма===
 +
Как и было сказано выше, основную часть метода занимают сравнения и перестановки.
 +
 
===Схема реализации последовательного алгоритма===
 
===Схема реализации последовательного алгоритма===
 +
Реализация последовательного алгоритма на языке c++:
 +
<source lang="c++">
 +
void bubbleSort(int arr[], int n)
 +
{
 +
    int i, j;
 +
    for (i = 0; i < n - 1; i++) 
 +
        for (j = 0; j < n - i - 1; j++)
 +
            if (arr[j] > arr[j + 1])
 +
                swap(arr[j], arr[j + 1]);
 +
}
 +
</source>
 +
 
===Последовательная сложность алгоритма===
 
===Последовательная сложность алгоритма===
 +
Относится к алгоритмам с квадратичной сложностью - o(n<sup>2</sup>)
 +
 
===Информационный граф===
 
===Информационный граф===
 
===Ресурс параллелизма алгоритма===
 
===Ресурс параллелизма алгоритма===
Строка 22: Строка 41:
  
 
===Свойства алгоритма===
 
===Свойства алгоритма===
 +
 
==Программная реализация алгоритма==
 
==Программная реализация алгоритма==
 
===Особенности реализации последовательного алгоритма===
 
===Особенности реализации последовательного алгоритма===

Версия 18:56, 22 ноября 2023

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

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 Вычислительное ядро алгоритма

Вычислительное ядро последовательной версии сортировки пузырьком можно составить из, в худшем случае, [math]\frac{n (n - 1)}{2}[/math] сравнений и обменов.

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

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

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

Реализация последовательного алгоритма на языке c++:

void bubbleSort(int arr[], int n) 
{ 
    int i, j; 
    for (i = 0; i < n - 1; i++)  
        for (j = 0; j < n - i - 1; j++) 
            if (arr[j] > arr[j + 1]) 
                swap(arr[j], arr[j + 1]); 
}

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

Относится к алгоритмам с квадратичной сложностью - o(n2)

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