Алговики - Вклад [ru]

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

2023-12-05T18:33:28Z

Alexeyshekhanov: /* Математическое описание алгоритма */

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

=== Математическое описание алгоритма ===
Давайте представим список из n элементов, обозначим его как <math>A[0], A[1], ..., A[n-1]</math>. Сортировка пузырьком выполняет следующие шаги: 1. Начнем с индекса <math>i = 0</math>. 2. Для каждого <math>i</math> от <math>0</math> до <math>n - 1</math>, сравниваем <math>A[i]</math> и <math>A[i+1]</math>. 3. Если <math>A[i] > A[i+1]</math>, меняем их местами. 4. После первого прохода самый большой элемент окажется в конце списка. 5. Уменьшаем 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>

===Последовательная сложность алгоритма===
Относится к алгоритмам с квадратичной сложностью - <math display="inline">\Theta(n^2)</math>

===Информационный граф===
Информационный граф состоит из <math>n</math> итераций, где разбиение элементов на пары начинается с нулевого элемента на каждой четной начинается, а на каждой нечетной с первого. Каждую такую пару может обрабатывать отдельный поток, независимо от других.
[[Файл:Информационный граф1.png|мини|Рис 1. Информационный граф алгоритма сортировки пузырьком]]
Это можно увидеть на примере, который изображен на рис. 2. Красным обведены элементы, которые сравниваются и "обмениваются" на данной итерации.

===Ресурс параллелизма алгоритма===
Ресурсом параллелизма в данном алгоритме является возможность независимого выполнения операций сравнения двух соседних элементов и последующего обмена этих элементов. Эти вызовы обрабатывают разные части данных и не зависят друг от друга, что позволяет выполнять их одновременно на разных потоках.

[[Файл:Example.jpg|мини|Рис 2. Пример с массивом размера 6, количеством потоков 3]]

В параллельной версии сортировки пузырьком мы каждую пару последовательно стоящих в массиве элементов подаем на отдельный поток. Это означает, что в идеальном случае (количество потоков неограниченно, затраты на создание потоков и синхронизацию между ними игнорируются) операции сравнения и замены индексов могут выполняться одновременно. Таким образом каждый шаг сортировки имеет временную сложность <math display="inline">\Theta(1)</math>, а максимальное время, необходимое для сортировки, будет n, соответственно временная сложность будет <math display="inline">\Theta(n)</math>.

Но на практике, когда ресурсы ограничены, получается, что при количестве потоков равном p, временная сложность становится <math display="inline">\Theta(\frac{n^2}{p})</math>.

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

==Программная реализация алгоритма==
===Особенности реализации последовательного алгоритма===
===Локальность данных и вычислений===
===Возможные способы и особенности параллельной реализации алгоритма===
===Масштабируемость алгоритма и его реализации===
Масштабируемость алгоритма сортировки пузырьком определяется размером входных данных и количеством доступных потоков.
1. В случае с входными данными, чем больше их размер, тем лучше масштабируемость.
2. В случае же с доступными потоками, то не всегда их число прямо пропорционально влияет на скорость выполнения сортировки. С какого то количества потоков, в зависимости от размера входных данных, сортировка начинает выполняться все медленнее и медленнее из за накладных расходов, таких как создание потоков, их синхронизация и т.п.
<gallery>
4kb.png|Зависимость времени сортировки от количества потоков при размере входных данных 4 Кбайт.
40kb.png|Зависимость времени сортировки от количества потоков при размере входных данных 40 Кбайт.
400kb.png|Зависимость времени сортировки от количества потоков при размере входных данных 400 Кбайт.
4mb.png|Зависимость времени сортировки от количества потоков при размере входных данных 4 Мбайт.
</gallery>

===Динамические характеристики и эффективность реализации алгоритма===
===Выводы для классов архитектур===
===Существующие реализации алгоритма===
Посмотрим на некоторые существующие улучшения последовательной сортировки пузырьком.

1) Реализация с проверкой обмена.
<source lang="c++">
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;
}
}
</source>
В данной реализации прирост скорости выполнения происходит за счет введения переменной swapped, и проверки ее значения. Конечно не во всех ситуациях, но некоторых массивах данный вариант будет работать быстрее.

2) Четная - нечетная сортировка
<source lang="c++">
void oddEvenBubbleSort(int *arr, int n, int threadsNumber)
{
int i, j;
for (i = 0; i < n; i++)
{
int first = i % 2;

for (j = first; j < n - 1; j+=2)
{
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
}
}
</source>
Этот вариант сортировки на случайно заполненных массивах показывал лучшее время из вышеупомянутых. Но главное его преимущество в том, данный алгоритм удобнее всего распараллеливать.

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

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

2023-12-05T18:32:28Z

Alexeyshekhanov: /* Информационный граф */

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

=== Математическое описание алгоритма ===
Давайте представим список из n элементов, обозначим его как <math>A[0], A[1], ..., A[n-1]</math>. Сортировка пузырьком выполняет следующие шаги: Начнем с индекса <math>i = 0</math>. Для каждого <math>i</math> от <math>0</math> до <math>n - 1</math>, сравниваем <math>A[i]</math> и <math>A[i+1]</math>. Если <math>A[i] > A[i+1]</math>, меняем их местами. После первого прохода самый большой элемент окажется в конце списка. Уменьшаем 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>

===Последовательная сложность алгоритма===
Относится к алгоритмам с квадратичной сложностью - <math display="inline">\Theta(n^2)</math>

===Информационный граф===
Информационный граф состоит из <math>n</math> итераций, где разбиение элементов на пары начинается с нулевого элемента на каждой четной начинается, а на каждой нечетной с первого. Каждую такую пару может обрабатывать отдельный поток, независимо от других.
[[Файл:Информационный граф1.png|мини|Рис 1. Информационный граф алгоритма сортировки пузырьком]]
Это можно увидеть на примере, который изображен на рис. 2. Красным обведены элементы, которые сравниваются и "обмениваются" на данной итерации.

===Ресурс параллелизма алгоритма===
Ресурсом параллелизма в данном алгоритме является возможность независимого выполнения операций сравнения двух соседних элементов и последующего обмена этих элементов. Эти вызовы обрабатывают разные части данных и не зависят друг от друга, что позволяет выполнять их одновременно на разных потоках.

[[Файл:Example.jpg|мини|Рис 2. Пример с массивом размера 6, количеством потоков 3]]

В параллельной версии сортировки пузырьком мы каждую пару последовательно стоящих в массиве элементов подаем на отдельный поток. Это означает, что в идеальном случае (количество потоков неограниченно, затраты на создание потоков и синхронизацию между ними игнорируются) операции сравнения и замены индексов могут выполняться одновременно. Таким образом каждый шаг сортировки имеет временную сложность <math display="inline">\Theta(1)</math>, а максимальное время, необходимое для сортировки, будет n, соответственно временная сложность будет <math display="inline">\Theta(n)</math>.

Но на практике, когда ресурсы ограничены, получается, что при количестве потоков равном p, временная сложность становится <math display="inline">\Theta(\frac{n^2}{p})</math>.

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

==Программная реализация алгоритма==
===Особенности реализации последовательного алгоритма===
===Локальность данных и вычислений===
===Возможные способы и особенности параллельной реализации алгоритма===
===Масштабируемость алгоритма и его реализации===
Масштабируемость алгоритма сортировки пузырьком определяется размером входных данных и количеством доступных потоков.
1. В случае с входными данными, чем больше их размер, тем лучше масштабируемость.
2. В случае же с доступными потоками, то не всегда их число прямо пропорционально влияет на скорость выполнения сортировки. С какого то количества потоков, в зависимости от размера входных данных, сортировка начинает выполняться все медленнее и медленнее из за накладных расходов, таких как создание потоков, их синхронизация и т.п.
<gallery>
4kb.png|Зависимость времени сортировки от количества потоков при размере входных данных 4 Кбайт.
40kb.png|Зависимость времени сортировки от количества потоков при размере входных данных 40 Кбайт.
400kb.png|Зависимость времени сортировки от количества потоков при размере входных данных 400 Кбайт.
4mb.png|Зависимость времени сортировки от количества потоков при размере входных данных 4 Мбайт.
</gallery>

===Динамические характеристики и эффективность реализации алгоритма===
===Выводы для классов архитектур===
===Существующие реализации алгоритма===
Посмотрим на некоторые существующие улучшения последовательной сортировки пузырьком.

1) Реализация с проверкой обмена.
<source lang="c++">
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;
}
}
</source>
В данной реализации прирост скорости выполнения происходит за счет введения переменной swapped, и проверки ее значения. Конечно не во всех ситуациях, но некоторых массивах данный вариант будет работать быстрее.

2) Четная - нечетная сортировка
<source lang="c++">
void oddEvenBubbleSort(int *arr, int n, int threadsNumber)
{
int i, j;
for (i = 0; i < n; i++)
{
int first = i % 2;

for (j = first; j < n - 1; j+=2)
{
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
}
}
</source>
Этот вариант сортировки на случайно заполненных массивах показывал лучшее время из вышеупомянутых. Но главное его преимущество в том, данный алгоритм удобнее всего распараллеливать.

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

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

2023-12-05T18:30:04Z

Alexeyshekhanov: /* Масштабируемость алгоритма и его реализации */

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

=== Математическое описание алгоритма ===
Давайте представим список из n элементов, обозначим его как <math>A[0], A[1], ..., A[n-1]</math>. Сортировка пузырьком выполняет следующие шаги: Начнем с индекса <math>i = 0</math>. Для каждого <math>i</math> от <math>0</math> до <math>n - 1</math>, сравниваем <math>A[i]</math> и <math>A[i+1]</math>. Если <math>A[i] > A[i+1]</math>, меняем их местами. После первого прохода самый большой элемент окажется в конце списка. Уменьшаем 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>

===Последовательная сложность алгоритма===
Относится к алгоритмам с квадратичной сложностью - <math display="inline">\Theta(n^2)</math>

===Информационный граф===
Информационный граф состоит из <math>n</math> итераций, где разбиение элементов на пары начинается с нулевого элемента на каждой четной начинается, а на каждой нечетной с первого. Каждую такую пару может обрабатывать отдельный поток, независимо от других.
[[Файл:Информационный граф1.png|мини|Рис 1. Информационный граф алгоритма сортировки пузырьком]]
Это можно увидеть на примере, который изображен на рис. 2

===Ресурс параллелизма алгоритма===
Ресурсом параллелизма в данном алгоритме является возможность независимого выполнения операций сравнения двух соседних элементов и последующего обмена этих элементов. Эти вызовы обрабатывают разные части данных и не зависят друг от друга, что позволяет выполнять их одновременно на разных потоках.

[[Файл:Example.jpg|мини|Рис 2. Пример с массивом размера 6, количеством потоков 3]]

В параллельной версии сортировки пузырьком мы каждую пару последовательно стоящих в массиве элементов подаем на отдельный поток. Это означает, что в идеальном случае (количество потоков неограниченно, затраты на создание потоков и синхронизацию между ними игнорируются) операции сравнения и замены индексов могут выполняться одновременно. Таким образом каждый шаг сортировки имеет временную сложность <math display="inline">\Theta(1)</math>, а максимальное время, необходимое для сортировки, будет n, соответственно временная сложность будет <math display="inline">\Theta(n)</math>.

Но на практике, когда ресурсы ограничены, получается, что при количестве потоков равном p, временная сложность становится <math display="inline">\Theta(\frac{n^2}{p})</math>.

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

==Программная реализация алгоритма==
===Особенности реализации последовательного алгоритма===
===Локальность данных и вычислений===
===Возможные способы и особенности параллельной реализации алгоритма===
===Масштабируемость алгоритма и его реализации===
Масштабируемость алгоритма сортировки пузырьком определяется размером входных данных и количеством доступных потоков.
1. В случае с входными данными, чем больше их размер, тем лучше масштабируемость.
2. В случае же с доступными потоками, то не всегда их число прямо пропорционально влияет на скорость выполнения сортировки. С какого то количества потоков, в зависимости от размера входных данных, сортировка начинает выполняться все медленнее и медленнее из за накладных расходов, таких как создание потоков, их синхронизация и т.п.
<gallery>
4kb.png|Зависимость времени сортировки от количества потоков при размере входных данных 4 Кбайт.
40kb.png|Зависимость времени сортировки от количества потоков при размере входных данных 40 Кбайт.
400kb.png|Зависимость времени сортировки от количества потоков при размере входных данных 400 Кбайт.
4mb.png|Зависимость времени сортировки от количества потоков при размере входных данных 4 Мбайт.
</gallery>

===Динамические характеристики и эффективность реализации алгоритма===
===Выводы для классов архитектур===
===Существующие реализации алгоритма===
Посмотрим на некоторые существующие улучшения последовательной сортировки пузырьком.

1) Реализация с проверкой обмена.
<source lang="c++">
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;
}
}
</source>
В данной реализации прирост скорости выполнения происходит за счет введения переменной swapped, и проверки ее значения. Конечно не во всех ситуациях, но некоторых массивах данный вариант будет работать быстрее.

2) Четная - нечетная сортировка
<source lang="c++">
void oddEvenBubbleSort(int *arr, int n, int threadsNumber)
{
int i, j;
for (i = 0; i < n; i++)
{
int first = i % 2;

for (j = first; j < n - 1; j+=2)
{
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
}
}
</source>
Этот вариант сортировки на случайно заполненных массивах показывал лучшее время из вышеупомянутых. Но главное его преимущество в том, данный алгоритм удобнее всего распараллеливать.

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

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

2023-12-05T18:26:43Z

Alexeyshekhanov: /* Масштабируемость алгоритма и его реализации */

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

=== Математическое описание алгоритма ===
Давайте представим список из n элементов, обозначим его как <math>A[0], A[1], ..., A[n-1]</math>. Сортировка пузырьком выполняет следующие шаги: Начнем с индекса <math>i = 0</math>. Для каждого <math>i</math> от <math>0</math> до <math>n - 1</math>, сравниваем <math>A[i]</math> и <math>A[i+1]</math>. Если <math>A[i] > A[i+1]</math>, меняем их местами. После первого прохода самый большой элемент окажется в конце списка. Уменьшаем 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>

===Последовательная сложность алгоритма===
Относится к алгоритмам с квадратичной сложностью - <math display="inline">\Theta(n^2)</math>

===Информационный граф===
Информационный граф состоит из <math>n</math> итераций, где разбиение элементов на пары начинается с нулевого элемента на каждой четной начинается, а на каждой нечетной с первого. Каждую такую пару может обрабатывать отдельный поток, независимо от других.
[[Файл:Информационный граф1.png|мини|Рис 1. Информационный граф алгоритма сортировки пузырьком]]
Это можно увидеть на примере, который изображен на рис. 2

===Ресурс параллелизма алгоритма===
Ресурсом параллелизма в данном алгоритме является возможность независимого выполнения операций сравнения двух соседних элементов и последующего обмена этих элементов. Эти вызовы обрабатывают разные части данных и не зависят друг от друга, что позволяет выполнять их одновременно на разных потоках.

[[Файл:Example.jpg|мини|Рис 2. Пример с массивом размера 6, количеством потоков 3]]

В параллельной версии сортировки пузырьком мы каждую пару последовательно стоящих в массиве элементов подаем на отдельный поток. Это означает, что в идеальном случае (количество потоков неограниченно, затраты на создание потоков и синхронизацию между ними игнорируются) операции сравнения и замены индексов могут выполняться одновременно. Таким образом каждый шаг сортировки имеет временную сложность <math display="inline">\Theta(1)</math>, а максимальное время, необходимое для сортировки, будет n, соответственно временная сложность будет <math display="inline">\Theta(n)</math>.

Но на практике, когда ресурсы ограничены, получается, что при количестве потоков равном p, временная сложность становится <math display="inline">\Theta(\frac{n^2}{p})</math>.

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

==Программная реализация алгоритма==
===Особенности реализации последовательного алгоритма===
===Локальность данных и вычислений===
===Возможные способы и особенности параллельной реализации алгоритма===
===Масштабируемость алгоритма и его реализации===
<gallery>
4kb.jpg|Зависимость времени сортировки от количества потоков при размере входных данных 4 Кбайт.
40kb.jpg|Зависимость времени сортировки от количества потоков при размере входных данных 40 Кбайт.
400kb.jpg|Зависимость времени сортировки от количества потоков при размере входных данных 400 Кбайт.
4mb.jpg|Зависимость времени сортировки от количества потоков при размере входных данных 4 Мбайт.
</gallery>

===Динамические характеристики и эффективность реализации алгоритма===
===Выводы для классов архитектур===
===Существующие реализации алгоритма===
Посмотрим на некоторые существующие улучшения последовательной сортировки пузырьком.

1) Реализация с проверкой обмена.
<source lang="c++">
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;
}
}
</source>
В данной реализации прирост скорости выполнения происходит за счет введения переменной swapped, и проверки ее значения. Конечно не во всех ситуациях, но некоторых массивах данный вариант будет работать быстрее.

2) Четная - нечетная сортировка
<source lang="c++">
void oddEvenBubbleSort(int *arr, int n, int threadsNumber)
{
int i, j;
for (i = 0; i < n; i++)
{
int first = i % 2;

for (j = first; j < n - 1; j+=2)
{
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
}
}
</source>
Этот вариант сортировки на случайно заполненных массивах показывал лучшее время из вышеупомянутых. Но главное его преимущество в том, данный алгоритм удобнее всего распараллеливать.

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

Файл:4mb.png

2023-12-05T18:25:07Z

Alexeyshekhanov:

4mb

Файл:400kb.png

2023-12-05T18:24:44Z

Alexeyshekhanov:

400kb

Файл:40kb.png

2023-12-05T18:24:20Z

Alexeyshekhanov:

40kb

Файл:4kb.png

2023-12-05T18:23:53Z

Alexeyshekhanov:

4kb

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

2023-12-05T18:16:49Z

Alexeyshekhanov: /* Информационный граф */

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

=== Математическое описание алгоритма ===
Давайте представим список из n элементов, обозначим его как <math>A[0], A[1], ..., A[n-1]</math>. Сортировка пузырьком выполняет следующие шаги: Начнем с индекса <math>i = 0</math>. Для каждого <math>i</math> от <math>0</math> до <math>n - 1</math>, сравниваем <math>A[i]</math> и <math>A[i+1]</math>. Если <math>A[i] > A[i+1]</math>, меняем их местами. После первого прохода самый большой элемент окажется в конце списка. Уменьшаем 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>

===Последовательная сложность алгоритма===
Относится к алгоритмам с квадратичной сложностью - <math display="inline">\Theta(n^2)</math>

===Информационный граф===
Информационный граф состоит из <math>n</math> итераций, где разбиение элементов на пары начинается с нулевого элемента на каждой четной начинается, а на каждой нечетной с первого. Каждую такую пару может обрабатывать отдельный поток, независимо от других.
[[Файл:Информационный граф1.png|мини|Рис 1. Информационный граф алгоритма сортировки пузырьком]]
Это можно увидеть на примере, который изображен на рис. 2

===Ресурс параллелизма алгоритма===
Ресурсом параллелизма в данном алгоритме является возможность независимого выполнения операций сравнения двух соседних элементов и последующего обмена этих элементов. Эти вызовы обрабатывают разные части данных и не зависят друг от друга, что позволяет выполнять их одновременно на разных потоках.

[[Файл:Example.jpg|мини|Рис 2. Пример с массивом размера 6, количеством потоков 3]]

В параллельной версии сортировки пузырьком мы каждую пару последовательно стоящих в массиве элементов подаем на отдельный поток. Это означает, что в идеальном случае (количество потоков неограниченно, затраты на создание потоков и синхронизацию между ними игнорируются) операции сравнения и замены индексов могут выполняться одновременно. Таким образом каждый шаг сортировки имеет временную сложность <math display="inline">\Theta(1)</math>, а максимальное время, необходимое для сортировки, будет n, соответственно временная сложность будет <math display="inline">\Theta(n)</math>.

Но на практике, когда ресурсы ограничены, получается, что при количестве потоков равном p, временная сложность становится <math display="inline">\Theta(\frac{n^2}{p})</math>.

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

==Программная реализация алгоритма==
===Особенности реализации последовательного алгоритма===
===Локальность данных и вычислений===
===Возможные способы и особенности параллельной реализации алгоритма===
===Масштабируемость алгоритма и его реализации===
===Динамические характеристики и эффективность реализации алгоритма===
===Выводы для классов архитектур===
===Существующие реализации алгоритма===
Посмотрим на некоторые существующие улучшения последовательной сортировки пузырьком.

1) Реализация с проверкой обмена.
<source lang="c++">
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;
}
}
</source>
В данной реализации прирост скорости выполнения происходит за счет введения переменной swapped, и проверки ее значения. Конечно не во всех ситуациях, но некоторых массивах данный вариант будет работать быстрее.

2) Четная - нечетная сортировка
<source lang="c++">
void oddEvenBubbleSort(int *arr, int n, int threadsNumber)
{
int i, j;
for (i = 0; i < n; i++)
{
int first = i % 2;

for (j = first; j < n - 1; j+=2)
{
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
}
}
</source>
Этот вариант сортировки на случайно заполненных массивах показывал лучшее время из вышеупомянутых. Но главное его преимущество в том, данный алгоритм удобнее всего распараллеливать.

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

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

2023-12-05T18:10:12Z

Alexeyshekhanov: /* Ресурс параллелизма алгоритма */

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

=== Математическое описание алгоритма ===
Давайте представим список из n элементов, обозначим его как <math>A[0], A[1], ..., A[n-1]</math>. Сортировка пузырьком выполняет следующие шаги: Начнем с индекса <math>i = 0</math>. Для каждого <math>i</math> от <math>0</math> до <math>n - 1</math>, сравниваем <math>A[i]</math> и <math>A[i+1]</math>. Если <math>A[i] > A[i+1]</math>, меняем их местами. После первого прохода самый большой элемент окажется в конце списка. Уменьшаем 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>

===Последовательная сложность алгоритма===
Относится к алгоритмам с квадратичной сложностью - <math display="inline">\Theta(n^2)</math>

===Информационный граф===
[[Файл:Информационный граф1.png|мини|Рис 1. Информационный граф алгоритма сортировки пузырьком]]

===Ресурс параллелизма алгоритма===
Ресурсом параллелизма в данном алгоритме является возможность независимого выполнения операций сравнения двух соседних элементов и последующего обмена этих элементов. Эти вызовы обрабатывают разные части данных и не зависят друг от друга, что позволяет выполнять их одновременно на разных потоках.

[[Файл:Example.jpg|мини|Рис 2. Пример с массивом размера 6, количеством потоков 3]]

В параллельной версии сортировки пузырьком мы каждую пару последовательно стоящих в массиве элементов подаем на отдельный поток. Это означает, что в идеальном случае (количество потоков неограниченно, затраты на создание потоков и синхронизацию между ними игнорируются) операции сравнения и замены индексов могут выполняться одновременно. Таким образом каждый шаг сортировки имеет временную сложность <math display="inline">\Theta(1)</math>, а максимальное время, необходимое для сортировки, будет n, соответственно временная сложность будет <math display="inline">\Theta(n)</math>.

Но на практике, когда ресурсы ограничены, получается, что при количестве потоков равном p, временная сложность становится <math display="inline">\Theta(\frac{n^2}{p})</math>.

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

==Программная реализация алгоритма==
===Особенности реализации последовательного алгоритма===
===Локальность данных и вычислений===
===Возможные способы и особенности параллельной реализации алгоритма===
===Масштабируемость алгоритма и его реализации===
===Динамические характеристики и эффективность реализации алгоритма===
===Выводы для классов архитектур===
===Существующие реализации алгоритма===
Посмотрим на некоторые существующие улучшения последовательной сортировки пузырьком.

1) Реализация с проверкой обмена.
<source lang="c++">
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;
}
}
</source>
В данной реализации прирост скорости выполнения происходит за счет введения переменной swapped, и проверки ее значения. Конечно не во всех ситуациях, но некоторых массивах данный вариант будет работать быстрее.

2) Четная - нечетная сортировка
<source lang="c++">
void oddEvenBubbleSort(int *arr, int n, int threadsNumber)
{
int i, j;
for (i = 0; i < n; i++)
{
int first = i % 2;

for (j = first; j < n - 1; j+=2)
{
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
}
}
</source>
Этот вариант сортировки на случайно заполненных массивах показывал лучшее время из вышеупомянутых. Но главное его преимущество в том, данный алгоритм удобнее всего распараллеливать.

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

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

2023-12-05T18:09:32Z

Alexeyshekhanov: /* Ресурс параллелизма алгоритма */

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

=== Математическое описание алгоритма ===
Давайте представим список из n элементов, обозначим его как <math>A[0], A[1], ..., A[n-1]</math>. Сортировка пузырьком выполняет следующие шаги: Начнем с индекса <math>i = 0</math>. Для каждого <math>i</math> от <math>0</math> до <math>n - 1</math>, сравниваем <math>A[i]</math> и <math>A[i+1]</math>. Если <math>A[i] > A[i+1]</math>, меняем их местами. После первого прохода самый большой элемент окажется в конце списка. Уменьшаем 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>

===Последовательная сложность алгоритма===
Относится к алгоритмам с квадратичной сложностью - <math display="inline">\Theta(n^2)</math>

===Информационный граф===
[[Файл:Информационный граф1.png|мини|Рис 1. Информационный граф алгоритма сортировки пузырьком]]

===Ресурс параллелизма алгоритма===
Ресурсом параллелизма в данном алгоритме является возможность независимого выполнения операций сравнения двух соседних элементов и последующего обмена этих элементов. Эти вызовы обрабатывают разные части данных и не зависят друг от друга, что позволяет выполнять их одновременно на разных потоках.

В параллельной версии сортировки пузырьком мы каждую пару последовательно стоящих в массиве элементов подаем на отдельный поток. Это означает, что в идеальном случае (количество потоков неограниченно, затраты на создание потоков и синхронизацию между ними игнорируются) операции сравнения и замены индексов могут выполняться одновременно. Таким образом каждый шаг сортировки имеет временную сложность <math display="inline">\Theta(1)</math>, а максимальное время, необходимое для сортировки, будет n, соответственно временная сложность будет <math display="inline">\Theta(n)</math>.

Но на практике, когда ресурсы ограничены, получается, что при количестве потоков равном p, временная сложность становится <math display="inline">\Theta(\frac{n^2}{p})</math>.
[[Файл:Example.jpg|мини|Рис 2. Пример с массивом размера 6, количеством потоков 3]]

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

==Программная реализация алгоритма==
===Особенности реализации последовательного алгоритма===
===Локальность данных и вычислений===
===Возможные способы и особенности параллельной реализации алгоритма===
===Масштабируемость алгоритма и его реализации===
===Динамические характеристики и эффективность реализации алгоритма===
===Выводы для классов архитектур===
===Существующие реализации алгоритма===
Посмотрим на некоторые существующие улучшения последовательной сортировки пузырьком.

1) Реализация с проверкой обмена.
<source lang="c++">
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;
}
}
</source>
В данной реализации прирост скорости выполнения происходит за счет введения переменной swapped, и проверки ее значения. Конечно не во всех ситуациях, но некоторых массивах данный вариант будет работать быстрее.

2) Четная - нечетная сортировка
<source lang="c++">
void oddEvenBubbleSort(int *arr, int n, int threadsNumber)
{
int i, j;
for (i = 0; i < n; i++)
{
int first = i % 2;

for (j = first; j < n - 1; j+=2)
{
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
}
}
</source>
Этот вариант сортировки на случайно заполненных массивах показывал лучшее время из вышеупомянутых. Но главное его преимущество в том, данный алгоритм удобнее всего распараллеливать.

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

Файл:Example.jpg

2023-12-05T18:08:26Z

Alexeyshekhanov:

Пример

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

2023-12-05T18:06:21Z

Alexeyshekhanov: /* Информационный граф */

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

=== Математическое описание алгоритма ===
Давайте представим список из n элементов, обозначим его как <math>A[0], A[1], ..., A[n-1]</math>. Сортировка пузырьком выполняет следующие шаги: Начнем с индекса <math>i = 0</math>. Для каждого <math>i</math> от <math>0</math> до <math>n - 1</math>, сравниваем <math>A[i]</math> и <math>A[i+1]</math>. Если <math>A[i] > A[i+1]</math>, меняем их местами. После первого прохода самый большой элемент окажется в конце списка. Уменьшаем 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>

===Последовательная сложность алгоритма===
Относится к алгоритмам с квадратичной сложностью - <math display="inline">\Theta(n^2)</math>

===Информационный граф===
[[Файл:Информационный граф1.png|мини|Рис 1. Информационный граф алгоритма сортировки пузырьком]]

===Ресурс параллелизма алгоритма===
Ресурсом параллелизма в данном алгоритме является возможность независимого выполнения операций сравнения двух соседних элементов и последующего обмена этих элементов. Эти вызовы обрабатывают разные части данных и не зависят друг от друга, что позволяет выполнять их одновременно на разных потоках.

В параллельной версии сортировки пузырьком мы каждую пару последовательно стоящих в массиве элементов подаем на отдельный поток. Это означает, что в идеальном случае (количество потоков неограниченно, затраты на создание потоков и синхронизацию между ними игнорируются) операции сравнения и замены индексов могут выполняться одновременно. Таким образом каждый шаг сортировки имеет временную сложность <math display="inline">\Theta(1)</math>, а максимальное время, необходимое для сортировки, будет n, соответственно временная сложность будет <math display="inline">\Theta(n)</math>.

Но на практике, когда ресурсы ограничены, получается, что при количестве потоков равном p, временная сложность становится <math display="inline">\Theta(\frac{n^2}{p})</math>.

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

==Программная реализация алгоритма==
===Особенности реализации последовательного алгоритма===
===Локальность данных и вычислений===
===Возможные способы и особенности параллельной реализации алгоритма===
===Масштабируемость алгоритма и его реализации===
===Динамические характеристики и эффективность реализации алгоритма===
===Выводы для классов архитектур===
===Существующие реализации алгоритма===
Посмотрим на некоторые существующие улучшения последовательной сортировки пузырьком.

1) Реализация с проверкой обмена.
<source lang="c++">
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;
}
}
</source>
В данной реализации прирост скорости выполнения происходит за счет введения переменной swapped, и проверки ее значения. Конечно не во всех ситуациях, но некоторых массивах данный вариант будет работать быстрее.

2) Четная - нечетная сортировка
<source lang="c++">
void oddEvenBubbleSort(int *arr, int n, int threadsNumber)
{
int i, j;
for (i = 0; i < n; i++)
{
int first = i % 2;

for (j = first; j < n - 1; j+=2)
{
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
}
}
</source>
Этот вариант сортировки на случайно заполненных массивах показывал лучшее время из вышеупомянутых. Но главное его преимущество в том, данный алгоритм удобнее всего распараллеливать.

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

Файл:Информационный граф1.png

2023-12-05T18:04:56Z

Alexeyshekhanov:

INFO

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

2023-12-05T17:58:16Z

Alexeyshekhanov: /* Ресурс параллелизма алгоритма */

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

=== Математическое описание алгоритма ===
Давайте представим список из n элементов, обозначим его как <math>A[0], A[1], ..., A[n-1]</math>. Сортировка пузырьком выполняет следующие шаги: Начнем с индекса <math>i = 0</math>. Для каждого <math>i</math> от <math>0</math> до <math>n - 1</math>, сравниваем <math>A[i]</math> и <math>A[i+1]</math>. Если <math>A[i] > A[i+1]</math>, меняем их местами. После первого прохода самый большой элемент окажется в конце списка. Уменьшаем 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>

===Последовательная сложность алгоритма===
Относится к алгоритмам с квадратичной сложностью - <math display="inline">\Theta(n^2)</math>

===Информационный граф===
[[Файл:Infograph2.jpg|мини|Рис.1. Информационный граф алгоритма сортировки пузырьком]]

===Ресурс параллелизма алгоритма===
Ресурсом параллелизма в данном алгоритме является возможность независимого выполнения операций сравнения двух соседних элементов и последующего обмена этих элементов. Эти вызовы обрабатывают разные части данных и не зависят друг от друга, что позволяет выполнять их одновременно на разных потоках.

В параллельной версии сортировки пузырьком мы каждую пару последовательно стоящих в массиве элементов подаем на отдельный поток. Это означает, что в идеальном случае (количество потоков неограниченно, затраты на создание потоков и синхронизацию между ними игнорируются) операции сравнения и замены индексов могут выполняться одновременно. Таким образом каждый шаг сортировки имеет временную сложность <math display="inline">\Theta(1)</math>, а максимальное время, необходимое для сортировки, будет n, соответственно временная сложность будет <math display="inline">\Theta(n)</math>.

Но на практике, когда ресурсы ограничены, получается, что при количестве потоков равном p, временная сложность становится <math display="inline">\Theta(\frac{n^2}{p})</math>.

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

==Программная реализация алгоритма==
===Особенности реализации последовательного алгоритма===
===Локальность данных и вычислений===
===Возможные способы и особенности параллельной реализации алгоритма===
===Масштабируемость алгоритма и его реализации===
===Динамические характеристики и эффективность реализации алгоритма===
===Выводы для классов архитектур===
===Существующие реализации алгоритма===
Посмотрим на некоторые существующие улучшения последовательной сортировки пузырьком.

1) Реализация с проверкой обмена.
<source lang="c++">
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;
}
}
</source>
В данной реализации прирост скорости выполнения происходит за счет введения переменной swapped, и проверки ее значения. Конечно не во всех ситуациях, но некоторых массивах данный вариант будет работать быстрее.

2) Четная - нечетная сортировка
<source lang="c++">
void oddEvenBubbleSort(int *arr, int n, int threadsNumber)
{
int i, j;
for (i = 0; i < n; i++)
{
int first = i % 2;

for (j = first; j < n - 1; j+=2)
{
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
}
}
</source>
Этот вариант сортировки на случайно заполненных массивах показывал лучшее время из вышеупомянутых. Но главное его преимущество в том, данный алгоритм удобнее всего распараллеливать.

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

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

2023-12-05T17:57:42Z

Alexeyshekhanov: /* Ресурс параллелизма алгоритма */

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

=== Математическое описание алгоритма ===
Давайте представим список из n элементов, обозначим его как <math>A[0], A[1], ..., A[n-1]</math>. Сортировка пузырьком выполняет следующие шаги: Начнем с индекса <math>i = 0</math>. Для каждого <math>i</math> от <math>0</math> до <math>n - 1</math>, сравниваем <math>A[i]</math> и <math>A[i+1]</math>. Если <math>A[i] > A[i+1]</math>, меняем их местами. После первого прохода самый большой элемент окажется в конце списка. Уменьшаем 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>

===Последовательная сложность алгоритма===
Относится к алгоритмам с квадратичной сложностью - <math display="inline">\Theta(n^2)</math>

===Информационный граф===
[[Файл:Infograph2.jpg|мини|Рис.1. Информационный граф алгоритма сортировки пузырьком]]

===Ресурс параллелизма алгоритма===
Ресурсом параллелизма в данном алгоритме является возможность независимого выполнения операций сравнения двух соседних элементов и последующего обмена этих элементов. Эти вызовы обрабатывают разные части данных и не зависят друг от друга, что позволяет выполнять их одновременно на разных потоках.

В параллельной версии сортировки пузырьком мы каждую пару последовательно стоящих в массиве элементов подаем на отдельный поток. Это означает, что в идеальном случае (количество потоков неограниченно, затраты на создание потоков и синхронизацию между ними игнорируются) операции сравнения и замены индексов могут выполняться одновременно. Таким образом каждый шаг сортировки имеет временную сложность О(1), а максимальное время, необходимое для сортировки, будет n, соответственно временная сложность будет О(n).

Но на практике, когда ресурсы ограничены, получается, что при количестве потоков равном p, временная сложность становится <math display="inline">\Theta(\frac{n^2}{p})</math>.

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

==Программная реализация алгоритма==
===Особенности реализации последовательного алгоритма===
===Локальность данных и вычислений===
===Возможные способы и особенности параллельной реализации алгоритма===
===Масштабируемость алгоритма и его реализации===
===Динамические характеристики и эффективность реализации алгоритма===
===Выводы для классов архитектур===
===Существующие реализации алгоритма===
Посмотрим на некоторые существующие улучшения последовательной сортировки пузырьком.

1) Реализация с проверкой обмена.
<source lang="c++">
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;
}
}
</source>
В данной реализации прирост скорости выполнения происходит за счет введения переменной swapped, и проверки ее значения. Конечно не во всех ситуациях, но некоторых массивах данный вариант будет работать быстрее.

2) Четная - нечетная сортировка
<source lang="c++">
void oddEvenBubbleSort(int *arr, int n, int threadsNumber)
{
int i, j;
for (i = 0; i < n; i++)
{
int first = i % 2;

for (j = first; j < n - 1; j+=2)
{
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
}
}
</source>
Этот вариант сортировки на случайно заполненных массивах показывал лучшее время из вышеупомянутых. Но главное его преимущество в том, данный алгоритм удобнее всего распараллеливать.

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

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

2023-12-05T17:56:53Z

Alexeyshekhanov: /* Информационный граф */

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

=== Математическое описание алгоритма ===
Давайте представим список из n элементов, обозначим его как <math>A[0], A[1], ..., A[n-1]</math>. Сортировка пузырьком выполняет следующие шаги: Начнем с индекса <math>i = 0</math>. Для каждого <math>i</math> от <math>0</math> до <math>n - 1</math>, сравниваем <math>A[i]</math> и <math>A[i+1]</math>. Если <math>A[i] > A[i+1]</math>, меняем их местами. После первого прохода самый большой элемент окажется в конце списка. Уменьшаем 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>

===Последовательная сложность алгоритма===
Относится к алгоритмам с квадратичной сложностью - <math display="inline">\Theta(n^2)</math>

===Информационный граф===
[[Файл:Infograph2.jpg|мини|Рис.1. Информационный граф алгоритма сортировки пузырьком]]

===Ресурс параллелизма алгоритма===
Ресурсом параллелизма в данном алгоритме является возможность независимого выполнения операций сравнения двух соседних элементов и последующего обмена этих элементов. Эти вызовы обрабатывают разные части данных и не зависят друг от друга, что позволяет выполнять их одновременно на разных потоках.

В параллельной версии сортировки пузырьком мы каждую пару последовательно стоящих в массиве элементов подаем на отдельный поток. Это означает, что в идеальном случае (количество потоков неограниченно, затраты на создание потоков и синхронизацию между ними игнорируются) операции сравнения и замены индексов могут выполняться одновременно. Таким образом каждый шаг сортировки имеет временную сложность О(1), а максимальное время, необходимое для сортировки, будет n, соответственно временная сложность будет О(n).

Но на практике, когда ресурсы ограничены, получается, что при количестве потоков равном p, временная сложность становится <math display="inline">\Theta(\frac{n^2}{p})</math>.

<gallery>
[[Файл:ParBubble2.png|мини|подпись]]
</gallery>

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

==Программная реализация алгоритма==
===Особенности реализации последовательного алгоритма===
===Локальность данных и вычислений===
===Возможные способы и особенности параллельной реализации алгоритма===
===Масштабируемость алгоритма и его реализации===
===Динамические характеристики и эффективность реализации алгоритма===
===Выводы для классов архитектур===
===Существующие реализации алгоритма===
Посмотрим на некоторые существующие улучшения последовательной сортировки пузырьком.

1) Реализация с проверкой обмена.
<source lang="c++">
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;
}
}
</source>
В данной реализации прирост скорости выполнения происходит за счет введения переменной swapped, и проверки ее значения. Конечно не во всех ситуациях, но некоторых массивах данный вариант будет работать быстрее.

2) Четная - нечетная сортировка
<source lang="c++">
void oddEvenBubbleSort(int *arr, int n, int threadsNumber)
{
int i, j;
for (i = 0; i < n; i++)
{
int first = i % 2;

for (j = first; j < n - 1; j+=2)
{
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
}
}
</source>
Этот вариант сортировки на случайно заполненных массивах показывал лучшее время из вышеупомянутых. Но главное его преимущество в том, данный алгоритм удобнее всего распараллеливать.

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

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

2023-12-05T17:55:15Z

Alexeyshekhanov: /* Информационный граф */

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

=== Математическое описание алгоритма ===
Давайте представим список из n элементов, обозначим его как <math>A[0], A[1], ..., A[n-1]</math>. Сортировка пузырьком выполняет следующие шаги: Начнем с индекса <math>i = 0</math>. Для каждого <math>i</math> от <math>0</math> до <math>n - 1</math>, сравниваем <math>A[i]</math> и <math>A[i+1]</math>. Если <math>A[i] > A[i+1]</math>, меняем их местами. После первого прохода самый большой элемент окажется в конце списка. Уменьшаем 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>

===Последовательная сложность алгоритма===
Относится к алгоритмам с квадратичной сложностью - <math display="inline">\Theta(n^2)</math>

===Информационный граф===
[[Файл:Infograph2.jpg|мини|info]]

===Ресурс параллелизма алгоритма===
Ресурсом параллелизма в данном алгоритме является возможность независимого выполнения операций сравнения двух соседних элементов и последующего обмена этих элементов. Эти вызовы обрабатывают разные части данных и не зависят друг от друга, что позволяет выполнять их одновременно на разных потоках.

В параллельной версии сортировки пузырьком мы каждую пару последовательно стоящих в массиве элементов подаем на отдельный поток. Это означает, что в идеальном случае (количество потоков неограниченно, затраты на создание потоков и синхронизацию между ними игнорируются) операции сравнения и замены индексов могут выполняться одновременно. Таким образом каждый шаг сортировки имеет временную сложность О(1), а максимальное время, необходимое для сортировки, будет n, соответственно временная сложность будет О(n).

Но на практике, когда ресурсы ограничены, получается, что при количестве потоков равном p, временная сложность становится <math display="inline">\Theta(\frac{n^2}{p})</math>.

<gallery>
[[Файл:ParBubble2.png|мини|подпись]]
</gallery>

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

==Программная реализация алгоритма==
===Особенности реализации последовательного алгоритма===
===Локальность данных и вычислений===
===Возможные способы и особенности параллельной реализации алгоритма===
===Масштабируемость алгоритма и его реализации===
===Динамические характеристики и эффективность реализации алгоритма===
===Выводы для классов архитектур===
===Существующие реализации алгоритма===
Посмотрим на некоторые существующие улучшения последовательной сортировки пузырьком.

1) Реализация с проверкой обмена.
<source lang="c++">
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;
}
}
</source>
В данной реализации прирост скорости выполнения происходит за счет введения переменной swapped, и проверки ее значения. Конечно не во всех ситуациях, но некоторых массивах данный вариант будет работать быстрее.

2) Четная - нечетная сортировка
<source lang="c++">
void oddEvenBubbleSort(int *arr, int n, int threadsNumber)
{
int i, j;
for (i = 0; i < n; i++)
{
int first = i % 2;

for (j = first; j < n - 1; j+=2)
{
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
}
}
</source>
Этот вариант сортировки на случайно заполненных массивах показывал лучшее время из вышеупомянутых. Но главное его преимущество в том, данный алгоритм удобнее всего распараллеливать.

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

Файл:Infograph2.jpg

2023-12-05T17:54:54Z

Alexeyshekhanov:

info

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

2023-12-05T17:53:28Z

Alexeyshekhanov: /* Последовательная сложность алгоритма */

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

=== Математическое описание алгоритма ===
Давайте представим список из n элементов, обозначим его как <math>A[0], A[1], ..., A[n-1]</math>. Сортировка пузырьком выполняет следующие шаги: Начнем с индекса <math>i = 0</math>. Для каждого <math>i</math> от <math>0</math> до <math>n - 1</math>, сравниваем <math>A[i]</math> и <math>A[i+1]</math>. Если <math>A[i] > A[i+1]</math>, меняем их местами. После первого прохода самый большой элемент окажется в конце списка. Уменьшаем 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>

===Последовательная сложность алгоритма===
Относится к алгоритмам с квадратичной сложностью - <math display="inline">\Theta(n^2)</math>

===Информационный граф===
===Ресурс параллелизма алгоритма===
Ресурсом параллелизма в данном алгоритме является возможность независимого выполнения операций сравнения двух соседних элементов и последующего обмена этих элементов. Эти вызовы обрабатывают разные части данных и не зависят друг от друга, что позволяет выполнять их одновременно на разных потоках.

В параллельной версии сортировки пузырьком мы каждую пару последовательно стоящих в массиве элементов подаем на отдельный поток. Это означает, что в идеальном случае (количество потоков неограниченно, затраты на создание потоков и синхронизацию между ними игнорируются) операции сравнения и замены индексов могут выполняться одновременно. Таким образом каждый шаг сортировки имеет временную сложность О(1), а максимальное время, необходимое для сортировки, будет n, соответственно временная сложность будет О(n).

Но на практике, когда ресурсы ограничены, получается, что при количестве потоков равном p, временная сложность становится <math display="inline">\Theta(\frac{n^2}{p})</math>.

<gallery>
[[Файл:ParBubble2.png|мини|подпись]]
</gallery>

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

==Программная реализация алгоритма==
===Особенности реализации последовательного алгоритма===
===Локальность данных и вычислений===
===Возможные способы и особенности параллельной реализации алгоритма===
===Масштабируемость алгоритма и его реализации===
===Динамические характеристики и эффективность реализации алгоритма===
===Выводы для классов архитектур===
===Существующие реализации алгоритма===
Посмотрим на некоторые существующие улучшения последовательной сортировки пузырьком.

1) Реализация с проверкой обмена.
<source lang="c++">
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;
}
}
</source>
В данной реализации прирост скорости выполнения происходит за счет введения переменной swapped, и проверки ее значения. Конечно не во всех ситуациях, но некоторых массивах данный вариант будет работать быстрее.

2) Четная - нечетная сортировка
<source lang="c++">
void oddEvenBubbleSort(int *arr, int n, int threadsNumber)
{
int i, j;
for (i = 0; i < n; i++)
{
int first = i % 2;

for (j = first; j < n - 1; j+=2)
{
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
}
}
</source>
Этот вариант сортировки на случайно заполненных массивах показывал лучшее время из вышеупомянутых. Но главное его преимущество в том, данный алгоритм удобнее всего распараллеливать.

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

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

2023-12-05T17:53:11Z

Alexeyshekhanov: /* Последовательная сложность алгоритма */

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

=== Математическое описание алгоритма ===
Давайте представим список из n элементов, обозначим его как <math>A[0], A[1], ..., A[n-1]</math>. Сортировка пузырьком выполняет следующие шаги: Начнем с индекса <math>i = 0</math>. Для каждого <math>i</math> от <math>0</math> до <math>n - 1</math>, сравниваем <math>A[i]</math> и <math>A[i+1]</math>. Если <math>A[i] > A[i+1]</math>, меняем их местами. После первого прохода самый большой элемент окажется в конце списка. Уменьшаем 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>

===Последовательная сложность алгоритма===
Относится к алгоритмам с квадратичной сложностью - <math display="inline">\Theta(n^2)</math></math>

===Информационный граф===
===Ресурс параллелизма алгоритма===
Ресурсом параллелизма в данном алгоритме является возможность независимого выполнения операций сравнения двух соседних элементов и последующего обмена этих элементов. Эти вызовы обрабатывают разные части данных и не зависят друг от друга, что позволяет выполнять их одновременно на разных потоках.

В параллельной версии сортировки пузырьком мы каждую пару последовательно стоящих в массиве элементов подаем на отдельный поток. Это означает, что в идеальном случае (количество потоков неограниченно, затраты на создание потоков и синхронизацию между ними игнорируются) операции сравнения и замены индексов могут выполняться одновременно. Таким образом каждый шаг сортировки имеет временную сложность О(1), а максимальное время, необходимое для сортировки, будет n, соответственно временная сложность будет О(n).

Но на практике, когда ресурсы ограничены, получается, что при количестве потоков равном p, временная сложность становится <math display="inline">\Theta(\frac{n^2}{p})</math>.

<gallery>
[[Файл:ParBubble2.png|мини|подпись]]
</gallery>

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

==Программная реализация алгоритма==
===Особенности реализации последовательного алгоритма===
===Локальность данных и вычислений===
===Возможные способы и особенности параллельной реализации алгоритма===
===Масштабируемость алгоритма и его реализации===
===Динамические характеристики и эффективность реализации алгоритма===
===Выводы для классов архитектур===
===Существующие реализации алгоритма===
Посмотрим на некоторые существующие улучшения последовательной сортировки пузырьком.

1) Реализация с проверкой обмена.
<source lang="c++">
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;
}
}
</source>
В данной реализации прирост скорости выполнения происходит за счет введения переменной swapped, и проверки ее значения. Конечно не во всех ситуациях, но некоторых массивах данный вариант будет работать быстрее.

2) Четная - нечетная сортировка
<source lang="c++">
void oddEvenBubbleSort(int *arr, int n, int threadsNumber)
{
int i, j;
for (i = 0; i < n; i++)
{
int first = i % 2;

for (j = first; j < n - 1; j+=2)
{
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
}
}
</source>
Этот вариант сортировки на случайно заполненных массивах показывал лучшее время из вышеупомянутых. Но главное его преимущество в том, данный алгоритм удобнее всего распараллеливать.

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

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

2023-12-05T17:52:27Z

Alexeyshekhanov: /* Макроструктура алгоритма */

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

=== Математическое описание алгоритма ===
Давайте представим список из n элементов, обозначим его как <math>A[0], A[1], ..., A[n-1]</math>. Сортировка пузырьком выполняет следующие шаги: Начнем с индекса <math>i = 0</math>. Для каждого <math>i</math> от <math>0</math> до <math>n - 1</math>, сравниваем <math>A[i]</math> и <math>A[i+1]</math>. Если <math>A[i] > A[i+1]</math>, меняем их местами. После первого прохода самый большой элемент окажется в конце списка. Уменьшаем 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>

===Последовательная сложность алгоритма===
Относится к алгоритмам с квадратичной сложностью - <math>o(n^2)</math>

===Информационный граф===
===Ресурс параллелизма алгоритма===
Ресурсом параллелизма в данном алгоритме является возможность независимого выполнения операций сравнения двух соседних элементов и последующего обмена этих элементов. Эти вызовы обрабатывают разные части данных и не зависят друг от друга, что позволяет выполнять их одновременно на разных потоках.

В параллельной версии сортировки пузырьком мы каждую пару последовательно стоящих в массиве элементов подаем на отдельный поток. Это означает, что в идеальном случае (количество потоков неограниченно, затраты на создание потоков и синхронизацию между ними игнорируются) операции сравнения и замены индексов могут выполняться одновременно. Таким образом каждый шаг сортировки имеет временную сложность О(1), а максимальное время, необходимое для сортировки, будет n, соответственно временная сложность будет О(n).

Но на практике, когда ресурсы ограничены, получается, что при количестве потоков равном p, временная сложность становится <math display="inline">\Theta(\frac{n^2}{p})</math>.

<gallery>
[[Файл:ParBubble2.png|мини|подпись]]
</gallery>

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

==Программная реализация алгоритма==
===Особенности реализации последовательного алгоритма===
===Локальность данных и вычислений===
===Возможные способы и особенности параллельной реализации алгоритма===
===Масштабируемость алгоритма и его реализации===
===Динамические характеристики и эффективность реализации алгоритма===
===Выводы для классов архитектур===
===Существующие реализации алгоритма===
Посмотрим на некоторые существующие улучшения последовательной сортировки пузырьком.

1) Реализация с проверкой обмена.
<source lang="c++">
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;
}
}
</source>
В данной реализации прирост скорости выполнения происходит за счет введения переменной swapped, и проверки ее значения. Конечно не во всех ситуациях, но некоторых массивах данный вариант будет работать быстрее.

2) Четная - нечетная сортировка
<source lang="c++">
void oddEvenBubbleSort(int *arr, int n, int threadsNumber)
{
int i, j;
for (i = 0; i < n; i++)
{
int first = i % 2;

for (j = first; j < n - 1; j+=2)
{
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
}
}
</source>
Этот вариант сортировки на случайно заполненных массивах показывал лучшее время из вышеупомянутых. Но главное его преимущество в том, данный алгоритм удобнее всего распараллеливать.

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

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

2023-12-05T17:51:10Z

Alexeyshekhanov: /* Свойства и структура алгоритма */

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

=== Математическое описание алгоритма ===
Давайте представим список из n элементов, обозначим его как <math>A[0], A[1], ..., A[n-1]</math>. Сортировка пузырьком выполняет следующие шаги: Начнем с индекса <math>i = 0</math>. Для каждого <math>i</math> от <math>0</math> до <math>n - 1</math>, сравниваем <math>A[i]</math> и <math>A[i+1]</math>. Если <math>A[i] > A[i+1]</math>, меняем их местами. После первого прохода самый большой элемент окажется в конце списка. Уменьшаем 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>

===Последовательная сложность алгоритма===
Относится к алгоритмам с квадратичной сложностью - <math>o(n^2)</math>

===Информационный граф===
===Ресурс параллелизма алгоритма===
Ресурсом параллелизма в данном алгоритме является возможность независимого выполнения операций сравнения двух соседних элементов и последующего обмена этих элементов. Эти вызовы обрабатывают разные части данных и не зависят друг от друга, что позволяет выполнять их одновременно на разных потоках.

В параллельной версии сортировки пузырьком мы каждую пару последовательно стоящих в массиве элементов подаем на отдельный поток. Это означает, что в идеальном случае (количество потоков неограниченно, затраты на создание потоков и синхронизацию между ними игнорируются) операции сравнения и замены индексов могут выполняться одновременно. Таким образом каждый шаг сортировки имеет временную сложность О(1), а максимальное время, необходимое для сортировки, будет n, соответственно временная сложность будет О(n).

Но на практике, когда ресурсы ограничены, получается, что при количестве потоков равном p, временная сложность становится <math display="inline">\Theta(\frac{n^2}{p})</math>.

<gallery>
[[Файл:ParBubble2.png|мини|подпись]]
</gallery>

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

==Программная реализация алгоритма==
===Особенности реализации последовательного алгоритма===
===Локальность данных и вычислений===
===Возможные способы и особенности параллельной реализации алгоритма===
===Масштабируемость алгоритма и его реализации===
===Динамические характеристики и эффективность реализации алгоритма===
===Выводы для классов архитектур===
===Существующие реализации алгоритма===
Посмотрим на некоторые существующие улучшения последовательной сортировки пузырьком.

1) Реализация с проверкой обмена.
<source lang="c++">
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;
}
}
</source>
В данной реализации прирост скорости выполнения происходит за счет введения переменной swapped, и проверки ее значения. Конечно не во всех ситуациях, но некоторых массивах данный вариант будет работать быстрее.

2) Четная - нечетная сортировка
<source lang="c++">
void oddEvenBubbleSort(int *arr, int n, int threadsNumber)
{
int i, j;
for (i = 0; i < n; i++)
{
int first = i % 2;

for (j = first; j < n - 1; j+=2)
{
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
}
}
</source>
Этот вариант сортировки на случайно заполненных массивах показывал лучшее время из вышеупомянутых. Но главное его преимущество в том, данный алгоритм удобнее всего распараллеливать.

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

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

2023-12-05T17:49:27Z

Alexeyshekhanov: /* Свойства и структура алгоритма */

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

=== Математическое описание алгоритма ===
Давайте представим список из n элементов, обозначим его как <math>A[0], A[1], ..., A[n-1]</math>. Сортировка пузырьком выполняет следующие шаги: Начнем с индекса <math>i = 0</math>. Для каждого <math>i</math> от <math>0</math> до <math>n - 1</math>, сравниваем <math>A[i]</math> и <math>A[i+1]</math>. Если <math>A[i] > A[i+1]</math>, меняем их местами. После первого прохода самый большой элемент окажется в конце списка. Уменьшаем 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>

===Последовательная сложность алгоритма===
Относится к алгоритмам с квадратичной сложностью - <math>o(n^2)</math>

===Информационный граф===
===Ресурс параллелизма алгоритма===
Ресурсом параллелизма в данном алгоритме является возможность независимого выполнения операций сравнения двух соседних элементов и последующего обмена этих элементов. Эти вызовы обрабатывают разные части данных и не зависят друг от друга, что позволяет выполнять их одновременно на разных потоках.

В параллельной версии сортировки пузырьком мы каждую пару последовательно стоящих в массиве элементов подаем на отдельный поток. Это означает, что в идеальном случае (количество потоков неограниченно, затраты на создание потоков и синхронизацию между ними игнорируются) операции сравнения и замены индексов могут выполняться одновременно. Таким образом каждый шаг сортировки имеет временную сложность О(1), а максимальное время, необходимое для сортировки, будет n, соответственно временная сложность будет О(n).

Но на практике, когда ресурсы ограничены, получается, что при количестве потоков равном p, временная сложность становится <math display="inline">\Theta(\n^2/p)</math>.

<gallery>
[[Файл:ParBubble2.png|мини|подпись]]
</gallery>

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

==Программная реализация алгоритма==
===Особенности реализации последовательного алгоритма===
===Локальность данных и вычислений===
===Возможные способы и особенности параллельной реализации алгоритма===
===Масштабируемость алгоритма и его реализации===
===Динамические характеристики и эффективность реализации алгоритма===
===Выводы для классов архитектур===
===Существующие реализации алгоритма===
Посмотрим на некоторые существующие улучшения последовательной сортировки пузырьком.

1) Реализация с проверкой обмена.
<source lang="c++">
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;
}
}
</source>
В данной реализации прирост скорости выполнения происходит за счет введения переменной swapped, и проверки ее значения. Конечно не во всех ситуациях, но некоторых массивах данный вариант будет работать быстрее.

2) Четная - нечетная сортировка
<source lang="c++">
void oddEvenBubbleSort(int *arr, int n, int threadsNumber)
{
int i, j;
for (i = 0; i < n; i++)
{
int first = i % 2;

for (j = first; j < n - 1; j+=2)
{
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
}
}
</source>
Этот вариант сортировки на случайно заполненных массивах показывал лучшее время из вышеупомянутых. Но главное его преимущество в том, данный алгоритм удобнее всего распараллеливать.

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

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

2023-12-05T12:56:47Z

Alexeyshekhanov: /* Ресурс параллелизма алгоритма */

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

=== Математическое описание алгоритма ===
Давайте представим список из n элементов, обозначим его как <math>A[0], A[1], ..., A[n-1]</math>. Сортировка пузырьком выполняет следующие шаги:
• Начнем с индекса <math>i = 0</math>.
• Для каждого <math>i</math> от <math>0</math> до <math>n - 1</math>, сравниваем <math>A[i]</math> и <math>A[i+1]</math>. Если <math>A[i] > A[i+1]</math>, меняем их местами.
• После первого прохода самый большой элемент окажется в конце списка.
• Уменьшаем 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>

===Последовательная сложность алгоритма===
Относится к алгоритмам с квадратичной сложностью - <math>o(n^2)</math>

===Информационный граф===
===Ресурс параллелизма алгоритма===
Ресурсом параллелизма в данном алгоритме является возможность независимого выполнения операций сравнения двух соседних элементов и последующего обмена этих элементов. Эти вызовы обрабатывают разные части данных и не зависят друг от друга, что позволяет выполнять их одновременно на разных потоках.

В параллельной версии сортировки пузырьком мы каждую пару последовательно стоящих в массиве элементов подаем на отдельный поток. Это означает, что в идеальном случае (количество потоков неограниченно, затраты на создание потоков и синхронизацию между ними игнорируются) операции сравнения и замены индексов могут выполняться одновременно. Таким образом каждый шаг сортировки имеет временную сложность О(1), а максимальное время, необходимое для сортировки, будет n, соответственно временная сложность будет О(n).

Но на практике, когда ресурсы ограничены, получается, что при количестве потоков равном p, временная сложность становится o(n^2/p).

<gallery>
[[Файл:ParBubble2.png|мини|подпись]]
</gallery>

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

==Программная реализация алгоритма==
===Особенности реализации последовательного алгоритма===
===Локальность данных и вычислений===
===Возможные способы и особенности параллельной реализации алгоритма===
===Масштабируемость алгоритма и его реализации===
===Динамические характеристики и эффективность реализации алгоритма===
===Выводы для классов архитектур===
===Существующие реализации алгоритма===
Посмотрим на некоторые существующие улучшения последовательной сортировки пузырьком.

1) Реализация с проверкой обмена.
<source lang="c++">
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;
}
}
</source>
В данной реализации прирост скорости выполнения происходит за счет введения переменной swapped, и проверки ее значения. Конечно не во всех ситуациях, но некоторых массивах данный вариант будет работать быстрее.

2) Четная - нечетная сортировка
<source lang="c++">
void oddEvenBubbleSort(int *arr, int n, int threadsNumber)
{
int i, j;
for (i = 0; i < n; i++)
{
int first = i % 2;

for (j = first; j < n - 1; j+=2)
{
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
}
}
</source>
Этот вариант сортировки на случайно заполненных массивах показывал лучшее время из вышеупомянутых. Но главное его преимущество в том, данный алгоритм удобнее всего распараллеливать.

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

Файл:ParBubble2.png

2023-12-05T12:55:42Z

Alexeyshekhanov:

Пример.

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

2023-12-05T12:46:33Z

Alexeyshekhanov: /* Последовательная сложность алгоритма */

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

2023-12-05T12:43:57Z

Alexeyshekhanov: /* Свойства и структура алгоритма */

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

2023-12-05T12:42:10Z

Alexeyshekhanov: /* Существующие реализации алгоритма */

Файл:ParBubble.png

2023-12-05T11:04:44Z

Alexeyshekhanov:

Пример. Параллельная сортировка пузырьком.

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

2023-12-05T10:39:02Z

Alexeyshekhanov: /* Математическое описание алгоритма */

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

2023-11-22T15:56:27Z

Alexeyshekhanov: /* Свойства и структура алгоритма */

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

2023-11-08T15:35:28Z

Alexeyshekhanov: /* Общее описание алгоритма */

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

2023-11-08T15:33:27Z

Alexeyshekhanov: /* Входные и выходные данные алгоритма */

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

2023-11-08T15:22:15Z

Alexeyshekhanov: /* Программная реализация алгоритма */

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

2023-10-31T16:57:12Z

Alexeyshekhanov: /* Литература */

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

2023-10-31T16:56:33Z

Alexeyshekhanov: добавлено описание последовательной реализации