Перейти к содержанию

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

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

Начинаем разбираться. Допустим у нас есть массив целых чисел, возьмем к примеру вот такую последовательность:

4 8 1 9 2 6

И нам нужно её отсортировать с помощью алгоритма пузырьковой сортировки. Алгоритм заключается в том, что мы последовательно попарно сверяем по 2 соседних элемента массива и если элемент справа меньше чем элемент слева, то они меняются местами. Более легкий элемент будто всплывает, отсюда и название алгоритма. После первого прохода по всему массиву самый тяжелый элемент осядет в конце списка. Давайте рассмотрим это на нашем примере:

4 8 1 9 2 6

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

4 8 1 9 2 6

Сравниваем по тому же принципу новую пару, 8 и 1. Первое число больше второго, а значит их нужно поменять местами. Напоминаю, более легкий элемент всплывает, более тяжелый тонет. Меняем местами и берем следующую пару чисел:

4 1 8 9 2 6

Как вы можете заметить, восьмерка опустилась ниже, единица всплыла. Берем следующую пару, это 8 и 9. Первое число меньше, значит оба остаются на своих позициях. Берем следующие:

4 1 8 9 2 6

Первое число больше второго, меняем местами и берем следующую пару:

4 1 8 2 9 6

И вот мы добрались до последней пары в нашем массиве. И снова первое число больше второго, значит меняем местами. По итогу полного прохода получаем вот такую картину:

4 1 8 2 6 9

Самый тяжелый элемент «ушел на дно». Теперь нам нужно повторить все наши действия с самого начала, но не трогать последний элемент, мы его выделили красным цветом. На втором круге делается всё тоже самое, поэтому не буду расписывать. После всей цепочки перестановок на 2 круге получим следующую картину:

4 1 8 2 6 9 1 4 8 2 6 9 1 4 8 2 6 9 1 4 2 8 6 9 — 1 4 2 6 8 9

Мы также сравнивали попарно и после второго круга у нас появился ещё один отсортированный элемент. Продолжаем все наши действия сначала и исключая уже отсортированные элементы до тех пор пока не отсортируется весь массив. Давайте реализуем всё это в программном коде:

//Создадим наш массив для сортировки
int[] arrayToSort = { 1, 3, 9, 5, 2, 6, 0, 4 };
//Получаем длину нашего массива
int len = arrayToSort.Length;
//Переменная для временного хранения значения при перестановке
int tmp;
//Цикл отвечает за количество проходов по массиву
for (int i = 0; i < len - 1; i++)
{
   //А в этом цикле мы перебираем элементы
   //условие j < len-1-i отвечает за то, чтобы на очередной итерации мы не брали уже отсортированные элементы
   //которые ушли на "дно" массива
   for (int j = 0; j < len-1-i; j++)
   {
       //Проверяем больше ли элемент в позиции j чем стоящий справа от него элемент в позиции j+1 
       if (arrayToSort[j] > arrayToSort[j+1])
       {
       //Если больше, тогда первый элемент из пары кладем во временную переменную tmp
       tmp = arrayToSort[j];
       //И ставим на позицию первого элемента, тот что стоит за ним
       arrayToSort[j] = arrayToSort[j+1];
       //И теперь на позицию второго элемента из пары помещаем значение из временной переменной
       arrayToSort[j+1] = tmp;
       }
       //Если первый элемент в паре оказался меньше, ничего не делаем и берем следующую пару
   }
}
#
Код на Python будет добавлен позже. 
#

Алгоритм пузырьковой сортировки имеет несколько улучшений и модификаций. Одно из них это использование флага проверки произошел ли обмен во время обхода элементов последовательности. Зачем это нужно ?

Массив ведь может прийти откуда угодно и не исключено что он уже отсортирован. Зачем нам в таком случае бегать по нему кругами ? Добавляем переменную-флажок и установим ему значение false, который будет переходить в значение true если на очередном переборе элементов массива была хоть одна перестановка. Если ни одной перестановки не произошло, значит массив полностью отсортирован и внешний (первый) цикл будет прерван. Модифицированный код будет выглядеть так:

int[] arrayToSort = { 1, 3, 9, 5, 2, 6, 0, 4 };
int len = arrayToSort.Length;
int tmp;
//Устанавливаем переменную флага в false
bool flag = false;

for (int i = 0; i < len - 1; i++)
{
//Перед началом внутреннего цикла нужно сбросить флаг в false
//иначе цикл завершится после первого обхода
   flag = false;
   for (int j = 0; j < len-1-i; j++)
   {
       if (arrayToSort[j] > arrayToSort[j+1])
       {
          tmp = arrayToSort[j];
          arrayToSort[j] = arrayToSort[j+1];
          arrayToSort[j+1] = tmp;
          //произошел обмен позициями, устанавливаем flag в true
          flag = true;
       }
   }
   //Проверяем флаг
   if (flag == false) break;
}

Новые строки подсвечены.

Сложность алгоритма

Алгоритм пузырьковой сортировки имеет сложность O (N2). Это значит что если мы сортируем массив из 10 элементов, то сложность алгоритма составит 10 в квадрате = 100. Не забываем, что сложность алгоритма O-большое оценивает алгоритм по наихудшему случаю когда мы достигаем конечного результата.

Практическое применение:
Алгоритм пузырьковой сортировки не имеет практического применения и практически не выходит за рамки учебной литературы.

 

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

Комментарии 1

Добавить комментарий

Ваш адрес email не будет опубликован.