Задача

1 /7


Пузырьковая сортировка

Теория Нажмите, чтобы прочитать/скрыть

Квадратичные сортировки

Сортировка - это перестановка элементов массива (списка) в заданном порядке.

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

Алгоритмическая реализация данного алгоритма
ЦИКЛ ДЛЯ J=1 ДО N-1 ШАГ 1
   F=0
   ЦИКЛ ДЛЯ I=1 ДО N-J-1 ШАГ 1
     ЕСЛИ A[I] > A[I+1] ТО 
       ОБМЕН A[I],A[I+1]
       F=1
   СЛЕДУЮЩЕЕ I 
   ЕСЛИ F=0 ТО ВЫХОД ИЗ ЦИКЛА   // если за проход не было обменов, 
                                // то значит все элементы 
                                // расставлены в нужном порядке
 СЛЕДУЮЩЕЕ J   
Сложность данного алгоритма: \(\displaystyle O(n^{2})\).


Дополнительная полезная информация: статья на википедии.

 

Задача

Требуется отсортировать массив по неубыванию методом "пузырька".
 
Входные данные
В первой строке вводится одно натуральное число N, не превосходящее 1000 – размер массива. Во второй строке задаются N чисел – элементы массива (целые числа, не превосходящие по модулю 1000).
 
Выходные данные
Вывести получившийся массив.
 
Примеры
Входные данные Выходные данные
1
5
5 4 3 2 1
1 2 3 4 5