Сортировка "пузырьком"
Сортировка "пузырьком"
Сортировка простыми обменами, сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяется сортировка вставками. Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.
ВикипедиЯ
Пузырьковая сортировка является очень простым алгоритмом и его временная сложность составляет O(n^2). Каждый раз, проходя по всему массиву, сначала мы сравниваем соседние элементы и если есть необходимость меняем их местами. Этот процесс повторяется, пока при очередном проходе сделана хотя бы одна замена. Предположим, что после T проходов массив уже отсортирован в порядке возрастания, тогда мы говорим, что T является количеством этапов соритовки для заданного массива. Ниже приведен пример. Возьмем за исходный начальный массив "5 14 2 8" а затем используя описанный алгоритм пузырьковой сортировки проведем его сортировку следующим образом:
Первый проход:
( 5 1 4 2 8 ) -> ( 1 5 4 2 8 ), сравнили первых два элемента и поменяли их местами.( 1 5 4 2 8 ) -> ( 1 4 5 2 8 ), поменяли местами 5 > 4( 1 4 5 2 8 ) -> ( 1 4 2 5 8 ), поменяли местами 5 > 2( 1 4 2 5 8 ) -> ( 1 4 2 5 8 ), так как два последних элемента упорядочены (8 > 5), алгоритм не меняет их местами.
Второй проход:
( 1 4 2 5 8 ) -> ( 1 4 2 5 8 ) ( 1 4 2 5 8 ) -> ( 1 2 4 5 8 ), поменяли местами 4 > 2 ( 1 2 4 5 8 ) -> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
После T = 2 проходов массив уже отсортирован, поэтому мы говорим, что количество проходов алгорима сортировки пузырьком для заданного массива равно 2.
Петя изучил алгоритм сортировки пузырьком в классе и его учитель задает задания, связанные с ним, как домашнее задание. Учитель предоставил Пете уже осортированный массив A состоящий из N различных целых чисел и утверждает, что он получил его после K проходов алгоримом сортировки пузырьком. Задание: какое количество исходных первоначальных массивов A может существовать, чтобы в итоге получить заданный массив после K проходов алгоритма сортировки пузырьком? Результат может быть очень большим, поэтому его необходимо вывести по модулю 20100713.
Входные данные
Входные данные состоят из нескольких тестов.
В первой строке задано натуральное число T (T ≤ 100000), указывающее количество тестовых случаев.
Следующие T строк содержат тестовые данные. В каждой строке находится два целых числа N и K (1 ≤ N ≤ 1000000, 0 ≤ K ≤ N - 1) где N указывает на размер массива, а K - количество этапов сортировки алгоритмом пузырька.
Выходные данные
Для каждого тестового случая вывести в отдельной строке ответ на поставленную задачу по модулю 20100713.
Пример
3 3 0 3 1 3 2
1 3 2
Примечание
Предположим, что задан массив {a, b, c} (a < b < c). Существует 6 различных вариантов исходного массива:
{a, b, c}, {a, c, b}, {b, a, c}, {b, c, a}, {c, a, b}, {c, b, a},
а исходный мы можем получить по разному:
{a, b, c}: не сортируя, так как массив уже отсортирован.
{a, c, b}, {b, a, c}, {c, a, b}: за один проход алгоритма сортировки пузырьком.
{b, c, a}, {c, b, a}: за 2 прохода алгоритма сортировки пузырьком.