⚙️ Алгоритмы · 20 вопросов · ~40 мин · ⏱ Таймер 40:00 · Средний · 👥 1 прошёл

Алгоритмы сортировки

Сортировка — не соревнование названий. Один метод выигрывает на почти готовом массиве, другой нужен для данных на диске, третий сохраняет порядок равных записей, а четвёртый даёт строгую гарантию худшего случая. Вопросы требуют проследить проходы, найти нарушение устойчивости и выбрать решение под конкретные ограничения.

Отвечено: 0 из 20

⏱ --:--

💡 Инструкция: Выбери один ответ из четырёх. В тесте 20 вопросов и 40 минут. После завершения откроются общий процент, четыре тематические шкалы, правильные ответы и пояснения.

Вопрос 1 из 20

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

a = [5, 1, 4, 2, 3]
for j in range(len(a) - 1):
    if a[j] > a[j + 1]:
        a[j], a[j + 1] = a[j + 1], a[j]
print(a)

[1, 4, 2, 3, 5] [1, 4, 5, 2, 3] [5, 1, 2, 3, 4] [1, 5, 4, 2, 3]

Вопрос 2 из 20

Какой массив получится после вставки элемента с индексом i=4?

a = [2, 4, 7, 9, 5, 8]
i = 4
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
    a[j + 1] = a[j]
    j -= 1
a[j + 1] = key
print(a)

[5, 2, 4, 7, 9, 8] [2, 4, 5, 7, 9, 8] [2, 4, 7, 9, 5, 8] [2, 4, 7, 5, 9, 8]

Вопрос 3 из 20

Сколько обменов выполнит сортировка выбором на массиве [1,2,3,4], если обмен делается только когда найденный минимум не стоит на текущем месте?

1 0 6 3

Вопрос 4 из 20

Сколько инверсий в массиве?

(i,j):\ i\lt j,\ a_i\gt a_j

a = [3, 1, 4, 2]
count = 0
for i in range(len(a)):
    for j in range(i + 1, len(a)):
        if a[i] > a[j]:
            count += 1
print(count)

3 5 2 4

Вопрос 5 из 20

Какая сортировка при проверке «были ли обмены» может завершиться за O(n) на уже отсортированном массиве?

Пирамидальная Выбором Обычная сортировка слиянием Пузырьковая с ранним выходом

Вопрос 6 из 20

Какой массив получится после этого разбиения относительно опорного элемента 4?

a = [6, 2, 7, 3, 5, 4]
pivot = a[-1]
i = 0
for j in range(len(a) - 1):
    if a[j] < pivot:
        a[i], a[j] = a[j], a[i]
        i += 1
a[i], a[-1] = a[-1], a[i]
print(a, i)

[2, 3, 4, 7, 6, 5] 2 [4, 2, 3, 6, 7, 5] 0 [2, 3, 4, 5, 6, 7] 2 [2, 3, 4, 6, 5, 7] 2

Вопрос 7 из 20

Какой результат вернёт слияние?

left = [1, 4, 8]
right = [2, 4, 7, 9]
i = j = 0
out = []
while i < len(left) and j < len(right):
    if left[i] <= right[j]:
        out.append(left[i]); i += 1
    else:
        out.append(right[j]); j += 1
out.extend(left[i:])
out.extend(right[j:])
print(out)

[1, 2, 4, 7, 8, 4, 9] [1, 2, 4, 4, 7, 8, 9] [1, 2, 4, 4, 8, 7, 9] [1, 4, 8, 2, 4, 7, 9]

Вопрос 8 из 20

Почему сортировка слиянием имеет O(n log n)?

T(n)=2T(n/2)+O(n)

Уровней O(log n), а суммарное слияние на каждом уровне O(n) Она сравнивает каждый элемент со всеми На каждом уровне выполняется O(log n), а уровней n Она использует хеш-таблицу

Вопрос 9 из 20

Какой вход наиболее опасен для этой реализации быстрой сортировки?

def quicksort(a):
    if len(a) < 2:
        return a
    pivot = a[0]
    left = [x for x in a[1:] if x < pivot]
    right = [x for x in a[1:] if x >= pivot]
    return quicksort(left) + [pivot] + quicksort(right)

Массив, где первый элемент близок к медиане Случайная перестановка разных чисел Уже отсортированный по возрастанию массив Массив из двух элементов в обратном порядке

Вопрос 10 из 20

Что даёт случайный выбор опорного элемента в быстрой сортировке?

Делает быструю сортировку устойчивой: равные ключи получают случайные фиксированные позиции Гарантирует O(n log n) в каждом запуске, включая неудачную последовательность опорных элементов Полностью устраняет рекурсию: обе части после выбора опорного элемента сортируются одним проходом Снижает вероятность систематически плохих разбиений, сохраняя ожидаемое O(n log n)

Вопрос 11 из 20

Какой порядок имён получится при устойчивой сортировке по score?

rows = [('Анна', 8), ('Борис', 5), ('Вера', 8), ('Глеб', 5)]
rows.sort(key=lambda x: x[1])
print([name for name, _ in rows])

[Борис, Глеб, Вера, Анна] [Глеб, Борис, Вера, Анна] [Анна, Вера, Борис, Глеб] [Борис, Глеб, Анна, Вера]

Вопрос 12 из 20

Данные сначала устойчиво отсортировали по фамилии, затем устойчиво по отделу. Какой итоговый порядок получится?

По отделу, а внутри одинакового отдела — по фамилии Только по фамилии, отдел потеряется Порядок будет случайным По фамилии, а внутри одинаковой фамилии — по отделу

Вопрос 13 из 20

Что нарушает устойчивость в этом фрагменте сортировки вставками?

for i in range(1, len(a)):
    key = a[i]
    j = i - 1
    while j >= 0 and a[j].score >= key.score:
        a[j + 1] = a[j]
        j -= 1
    a[j + 1] = key

Сравнение >= вместо > Начало с индекса 1 Использование цикла while Сдвиг элементов вправо

Вопрос 14 из 20

Почему обратный проход делает эту сортировку подсчётом устойчивой?

for x in a:
    count[key(x)] += 1
for i in range(1, len(count)):
    count[i] += count[i - 1]
for i in range(len(a) - 1, -1, -1):
    k = key(a[i])
    out[count[k] - 1] = a[i]
    count[k] -= 1

Обратный проход располагает ключи по убыванию, после чего результат разворачивается Поздние равные элементы занимают поздние позиции, не обгоняя ранние Обратный проход уменьшает дополнительную память до O(1), освобождая счётчики При движении справа налево накопленные суммы больше не нужны и не вычисляются

Вопрос 15 из 20

Как сделать неустойчивую сортировку пригодной для сохранения исходного порядка равных ключей?

После сортировки восстановить порядок равных элементов только по их значениям Добавить исходный индекс как второй компонент ключа Сначала отсортировать по индексу, а затем неустойчиво по основному ключу При равных ключах запретить обмен соседей, не меняя остальные шаги неустойчивого алгоритма

Вопрос 16 из 20

Какой алгоритм особенно уместен для почти отсортированного массива с несколькими локальными нарушениями?

T=O(n+k)

def insertion_sort(a):
    for i in range(1, len(a)):
        value = a[i]
        j = i - 1
        while j >= 0 and a[j] > value:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = value

# В массиве велико n, но число инверсий k мало.

Быстрая сортировка с первым элементом в роли опорного Сортировка вставками Пирамидальная сортировка с гарантией O(n log n), не использующая малое число инверсий Сортировка слиянием, сохраняющая O(n log n) и на почти упорядоченном входе

Вопрос 17 из 20

Файл значительно больше оперативной памяти. Какой подход обычно используют для сортировки?

Загрузить файл целиком и применить selection sort, полагаясь на виртуальную память Разбить на помещающиеся блоки, отсортировать их и выполнить внешнее многопутевое слияние Сохранить на диске все перестановки блоков и выбрать лексикографически минимальную Использовать рекурсивную быструю сортировку без внешних буферов со случайным чтением файла

Вопрос 18 из 20

Какая структура позволит получить пять наименьших элементов потока за O(n log 5) времени и O(5) дополнительной памяти?

def five_smallest(stream):
    candidates = []
    for value in stream:
        if len(candidates) < 5:
            add_candidate(candidates, value)
        elif value < current_largest_candidate(candidates):
            replace_largest_candidate(candidates, value)
    return candidates

# Поток содержит миллионы значений; весь поток хранить нельзя.

Отсортированный массив, в котором сохраняются все прочитанные элементы Min-куча размера 5: при переполнении удаляется её минимум Max-куча размера 5: новый меньший элемент заменяет текущий максимум кандидатов Max-куча всех элементов потока с пятью извлечениями после чтения

Вопрос 19 из 20

Какая сортировка гарантирует O(n log n) в худшем случае, работает на месте с O(1) дополнительной памятью и не обязана быть устойчивой?

Сортировка вставками Пирамидальная сортировка Сортировка слиянием стандартной массивной реализацией Сортировка подсчётом

Вопрос 20 из 20

Даны миллионы целых ключей от 0 до 999, нужна линейная по n сортировка. Что разумнее всего?

Быстрая сортировка с первым элементом в роли опорного Пузырьковая сортировка Сортировка подсчётом Полный перебор

Ответьте на все 20 вопросов, чтобы получить результат

🔗 Встроить тест на свой сайт (iframe) ▼

Скопируйте код и вставьте в любое место на вашем сайте:

Также доступна прямая ссылка на embed-страницу