В этом материале мы поговорим про алгоритм сортировки пузырьком (Bubble sort). Для примера попробуем отсортировать массив вручную, после чего напишем код для сортировки пузырьком на языке программирования Python и Си шарп.
Описание алгоритма
В процессе сортировки пузырьком происходит попарное сравнение соседних элементов массива, начиная с нулевого. После первой итерации самое большое число окажется на месте последнего, причем в дальнейших итерациях это значение уже задействоваться не будет (по сути, мы получим n-1 сравнений). Далее алгоритм находит второй по величине элемент, который ставится на предпоследнее место, потом третий и пр. В результате на месте нулевого элемента (не забываем, что нумерация в массиве начинается с нуля) окажется наименьшее число, а на месте последнего элемента – наибольшее. То есть мы можем сказать, что элементы от большего к меньшему «всплывают» по аналогии с пузырьками.
Проговорим алгоритм еще раз:
- Текущий элемент сравнивается с последующим.
- Если последующий меньше или больше, они меняются местами.
- Когда сортировка заканчивается, алгоритм прекращает работу, иначе снова происходит переход на шаг № 1.
Важно понимать, что при реализации сортировки применяют 2 цикла: основной и вложенный (внутренний цикл). По результатам одного прохода внутреннего цикла самый большой элемент смещается в конец массива, тогда как самый маленький перемещается к началу (на одну позицию).
Рассмотрим пример
Представьте, что у нас есть следующий массив:
7 2 9 4 1 0
В процессе первой итерации мы возьмем нулевой элемент (это 7) и сравним его с соседним. Так как семь больше двух, числа меняются своими местами. То есть массив меняется:
2 7 9 4 1 0
Потом происходит сравнение второго и третьего числа. Так как изначально 9 больше семи, то семь остается на месте. Далее 9 последовательно сравнивается с остальными значениями и таким образом постепенно перемещается в самый конец массива (так как числа, большего, чем 9, в массиве нет, девятка занимает заслуженное последнее место).
2 7 4 1 0 9
Первая итерация закончена, количество шагов уменьшилось на 1 (n-1), то есть 9 находится там, где надо. Больше это число не затрагивается.
Во второй итерации все опять начинается с нулевого элемента массива (в нашем случае это двойка) с последующими сравнениями и перемещениями. В результате массив будет выглядеть следующим образом:
2 4 1 0 7 9
И так далее. Итоговый вид массива после сортировки по методу пузырьком вы можете видеть ниже:
0 1 2 4 7 9
Как видите, ничего сложного в этом нет.
Реализация на Си шарп
Чтобы реализовать сортировку пузырьком, сначала над создать саму функцию сортировки, которая будет располагаться в итоге перед функцией main:
static int[] BubbleSort(int[] mas)
{
int temp;
for (int i = 0; i < mas.Length; i++)
{
for (int j = i + 1; j < mas.Length; j++)
{
if (mas[i] > mas[j])
{
temp = mas[i];
mas[i] = mas[j];
mas[j] = temp;
}
}
}
return mas;
}
Итоговый код будет выглядеть следующим образом:
Реализация на Python
Теперь давайте попробуем выполнить сортировку пузырьком c «Пайтон»:
По материалам:
- https://all-python.ru/primery/puzyryok.html;
- https://csharp.webdelphi.ru/sortirovka-massiva-c-algoritm-sortirovka-puzyrkom/;
- https://vscode.ru/prog-lessons/sortirovka-metodom-puzyirka-c-sharp.html.
