Модуль: (Python) Квадратичные сортировки


Задача

1 /8


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

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

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

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

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

Алгоритмическая реализация данного алгоритма
ЦИКЛ ДЛЯ 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

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w64685
Free Pascal2
Python1063
Комментарий учителя

Напишите программу

или выберите язык программирования и введите исходный код

Auto

       

Результат проверки программы 
Для проверки решения задачи необходимо зарегистрироваться или авторизоваться!