Алгоритмы и структуры данных · 14 из 17
Сколько стоит сортировка
В диспетчерской такси спорят, переписывать ли сортировку табло. Старая — пузырёк, новая — слиянием. Старший диспетчер не верит словам «быстрее» и просит посчитать честно: сколько раз каждая сортировка сравнивает две машины на одном и том же ряде. Сравнение — это то, что сортировка делает чаще всего, его и считают.
Что сделать
Отсортируйте список пузырьком или слиянием и верните, сколько раз сортировка сравнила два элемента.
Что приходит
algoritm—"puzyrek"или"sliyanie"xs— список чисел; его самого менять нельзя
Что вернуть
Число сравнений — целое.
Допишите функцию sravneniy в редакторе справа.
Результат верните через return — то, что
напечатано, на проверку не влияет.
с графикой когда тесты пройдут, ответ вашей функции нарисуется · все задачи с графикой
Пузырёк на [3, 1, 2]: первый проход сравнивает 3 с 1 (меняет) и 3 с 2 (меняет) — два сравнения; второй проход сравнивает 1 с 2, обменов нет — сортировка кончилась. Всего 3.
sravneniy("puzyrek", [3, 1, 2])
3
Сравнение — проверка, какой из двух элементов больше.
puzyrek: проход номер i (с нуля) сравнивает соседние пары слева направо, от первой до (n − 1 − i)-й, и меняет пару, где левое строго больше. Проход без обменов — конец. Проходов не больше n − 1. sliyanie: список длиной 0 или 1 готов без сравнений. Иначе его делят пополам: левая часть — первые len // 2 элементов, правая — остальные; каждую сортируют так же, затем сливают: пока в обеих частях что-то есть, сравнивают их первые элементы (одно сравнение) и берут меньший, при равенстве — из левой. Когда одна часть кончилась, остаток другой дописывается без сравнений. Ответ — сумма сравнений на всех уровнях.
Обсуждение
Вопросов пока нет.
Войдите, чтобы спросить.