Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Военная сортировка#54665

Фирма Macrohard получила заказ от армии одной страны на реализацию комплекса программного обеспечения для нового суперсекретного радара. Одной из наиболее важных подпрограмм в разрабатываемом комплексе является процедура сортировки.

Однако в отличие от обычной сортировки, эта процедура должна сортировать не произвольный массив чисел, который передается ей на вход, а специальный заранее заданный массив из N чисел, в котором записана некоторая фиксированная перестановка чисел от 1 до N, и кроме того, ни одно число в нем изначально не находится на своем месте (то есть на позиции с номером i изначально не находится число i).

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

Например, если массив из 6 элементов в некоторый момент имеет вид <2, 1, 3, 6, 4, 5>, то можно поменять местами 1 и 2, 6 и 4 или 4 и 5, а менять местами 1 и 3 или 3 и 6 нельзя, поскольку число 3 находится на своем месте (на позиции с номером 3).

Вам дан входной массив и поставлено важное задание. Найти последовательность обменов (не обязательно кратчайшую), сортирующую массив и удовлетворяющую приведенным условиям.

Подсказка

Найти такую последовательность обменов всегда возможно.

Входные данные
В первой строке вводится целое число N - размер входного массива (1 <= N <= 100). Вторая строка содержит N целых чисел - исходную перестановку чисел от 1 до N в массиве. Изначально ни одно число не стоит на своем месте.

Выходные данные
Выведите K строк, где K - количество обменов в Вашей сортировке. На каждой строке выведите по два числа x_i и y_i, разделенных пробелом - позиции в массиве, числа на которых следует поменять местами на i-ом обмене. Помните, что должно выполняться условие |x_i - y_i| = 1 и что нельзя перемещать число, которое уже стоит на своем месте.

Пояснение к примеру
В приведенном примере массив последовательно имеет следующий вид:
исходный вид массива
2 3 1 6 4 5
поменяли местами числа на 2 и 3 позициях
2 1 3 6 4 5
поменяли местами числа на 1 и 2 позициях
1 2 3 6 4 5
поменяли местами числа на 4 и 5 позициях
1 2 3 4 6 5
поменяли местами числа на 5 и 6 позициях
1 2 3 4 5 6

Сортировка "пузырьком"Сортировка выбором (максимума)

✓ 1✗ 2—Войти и решать

Out of Sorts#90035

Беси начал изучать алгоритмы с различных WEB-ресурсов.

Её любимый алгоритм - пузырьковая сортировка. Ниже приведена его реализация в коровьем коде, которая сортирует массив \(A\) длины \(N\).

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
         sorted = false

Команда "moo" выводит слово "moo".

По данному массиву предскажите, сколько раз будет напечатано слово "moo" этим кодом Беси.

ФОРМАТ ВВОДА (файл sort.in):

Первая строка ввода содержит \(N\) (\(1 \leq N \leq 100,000\)). Следующие \(N\) строк описывают \(A[0] \ldots A[N-1]\), каждая - целое число в интервале \(0 \ldots 10^9\). Не гарантируется, что все элементы различны.

ФОРМАТ ВЫВОДА (файл sort.out):

Выведите, сколько раз будет напечатано слово "moo"

Сортировка "пузырьком"

—Войти и решать

Out of Sorts#90028

Беси изучает алгоритмы на web-ресурсах.

Её любимый алгоритм называется "пузырьковая сортировка". Ниже приведена начальная его версия в коровьем коде для сортировки массива \(A\) из \(N\) элементов.

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
         sorted = false

Команда "moo" выводит слово "moo".

После тестирования кода на нескольких массивах, Беси сделала интересное наблюдение: в то время ка большие элементы становятся в конец массива очень быстро, маленькие элементы становятся в начало массива очень медленно. Для дальнейшего исследования проблемы, Беси модифицировала свой код так, чтобы её код сканировал элементы вперёд а затем назад на каждой итерации главного цикла, так чтобы и большие элементы и маленькие элементы быстро достигали границ массива. Ниже представлен её код.

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = N-2 downto 0:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         sorted = false

По заданному входному массиву предскажите, сколько раз слово "moo" будет напечатано этим модифицированным кодом.

ФОРМАТ ВВОДА (файл sort.in):

Первая строка ввода содержит \(N\) (\(1 \leq N \leq 100,000\)). Следующие \(N\) строк описывают \(A[0] \ldots A[N-1]\). Каждый элемент - целое число в интервале \(0 \ldots 10^9\). Не гарантируется, что все элементы различны.

ФОРМАТ ВЫВОДА (файл sort.out):

Выведите сколько раз meltn напечатано слово "moo".

Сортировка "пузырьком"

—Войти и решать

Сортировка выбором максимума#53617

Требуется отсортировать массив по неубыванию методом "выбор максимума".

Входные данные
В первой строке вводится одно натуральное число, не превосходящее 1000 – размер массива. Во второй строке задаются N чисел – элементы массива (целые числа, не превосходящие по модулю 1000).

Выходные данные
Вывести получившийся массив.

Сортировка выбором (максимума)

✓ 1✗ 0—Войти и решать