e-olymp 2663. Сортировка пузырьком

Условие

Определите, сколько обменов сделает алгоритм пузырьковой сортировки по возрастанию для данного массива.

Входные данные

В первой строке содержится количество элементов $n$ ($1 \leqslant n \leqslant 1000$) в массиве. Во второй строке — сам массив. Гарантируется, что все элементы массива различны и не превышают по модулю $10$$9$.

Выходные данные

Выведите одно число — количество обменов пузырьковой сортировки.

Тесты

Ввод Вывод
1 3
1 3 2
1
2 2
2 1
1
3 4
4 1 5 3
3
4 5
5 4 1 100000 7
4
5 6
6 5 4 3 2 1
15

Решение

Используем простой алгоритм пузырьковой сортировки: проходим по массиву циклом, если два элемента стоят не в том порядке, то меняем их местами. Так как задача состоит в том, чтобы вывести число обменов, при каждом обмене прибавляем к счётчику $1$. При каждом выполнении цикла по j ставится на место хотя бы 1 элемент, поэтому с каждым полным проходом его длина сокращается на $1$.

Код программы

Ссылки

решение на e-olymp
код на ideone

5 thoughts on “e-olymp 2663. Сортировка пузырьком

    • Функция проверки не вычисляет количество чего-либо в штуках. А значит тип возвращаемого значения не целый, а… Вот догадайтесь какой 😉
    • Каждый проход внутреннего цикла ставит на свое место как минимум одно значение. Следователь в дальнейшем его проверять ненужно. Значит внутренний цикл с каждым шагом становится все короче и короче. А у Вас не так.
  1. Почти. Ваше решение стоило бы записать так:

    Разберитесь, пожалуйста, какие исправления я вн’с и попробуйте догадаться почему?
    Но есть еще один важный момент. Если внутренний цикл не произвел ни одного обмена элементов, то массив уже отсортирован и следует закончить работу. Это несколько усложнит код, но в среднем сортировка будет проходить быстрее:

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