1.
Пузырьковая сортировка
Квадратичные сортировки
Сортировка - это перестановка элементов массива (списка) в заданном порядке.
Метод пузырька (пузырьковая сортировка), или сортировка простыми обменами).
Бессмертная классика жанра. Принцип действий прост: обходим массив от начала до конца, попутно меняя местами неотсортированные соседние элементы. В результате первого прохода на последнее место «всплывёт» максимальный элемент. Теперь снова обходим неотсортированную часть массива (от первого элемента до предпоследнего) и меняем по пути неотсортированных соседей. Второй по величине элемент окажется на предпоследнем месте. Продолжая в том же духе, будем обходить всё уменьшающуюся неотсортированную часть массива, запихивая найденные максимумы в конец.
Источник
Алгоритмическая реализация данного алгоритма
ЦИКЛ ДЛЯ 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 |
Запрещенные операторы: sort
Напишите программу
Auto