Постановка задачи: выполнить сортировку целых чисел по возрастанию методом пузырька

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

Последовательно сравниваем a[0] с a[1], затем a[1] с a[2] и так далее, меняя местами a[i] c a[i+1], если a[i]>a[i+1]. Таким образом, на последнем месте (номер n-1) в массиве окажется наибольшее значение. Например, цепочка преобразований для массива 8 10 2 4  $\Rightarrow$ 8 10 2 4 $\Rightarrow$ 8 2 10 4 $\Rightarrow$ 8 2 4 10. Далее опять просматриваем все пары элементов с самого начала, но до элемента с номером n-2. Тогда на предпоследнем месте окажется второе по величине значение. Аналогично продолжаем процесс. Если при очередном просмотре не было произведено ни одного обмена, значит, сортировку можно завершать досрочно (команда break).

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

Сложность сортировки: $\Theta (n^2)$

Код написан на С++. Индексы массива от 0 до n-1, если размер массива равен n.

к списку алгоритмов