Алгоритмы и структуры данных · 26 из 30
Быстрая сортировка по Ломуто
Лабораторная «сортировки», вторая часть. После вставок Борис Аркадьевич даёт быструю сортировку — как у Кормена, с разбиением
Ломуто: опорный — последний элемент отрезка, всё, что не больше него, сгоняется влево. Проверять он будет не только результат, но и число обменов: «sorted у вас и так есть. Мне нужен ваш алгоритм, шаг в шаг».
Что сделать
Отсортируйте список на месте быстрой сортировкой с разбиением Ломуто и сосчитайте, сколько было обменов.
Что приходит
a— список чисел; его и надо отсортировать, на месте
Что вернуть
Число обменов двух элементов, стоявших на разных местах; сам список после вызова — по возрастанию.
Допишите функцию bystraya в редакторе справа.
Результат верните через return — то, что
напечатано, на проверку не влияет.
Список [3, 1, 2], опорный — 2. Тройка больше опорного, единица — нет: она меняется местами с тройкой, это первый обмен, — [1, 3, 2]. Опорный встаёт на место тройки — второй обмен, [1, 2, 3]. Слева и справа от опорного по одному элементу, сортировать нечего: ответ 2, а список отсортирован.
a = [3, 1, 2]
(bystraya(a), a)
(2, [1, 2, 3])
Алгоритм — ровно такой:
разбить(lo, hi):
опорный = a[hi]; i = lo
для j от lo до hi − 1:
если a[j] <= опорный:
поменять a[i] и a[j]; i = i + 1
поменять a[i] и a[hi]
вернуть i
сортировать(lo, hi):
если lo < hi:
p = разбить(lo, hi)
сортировать(lo, p − 1)
сортировать(p + 1, hi)
Начало — сортировать(0, len(a) − 1). Сравнение нестрогое: равный опорному уходит влево. Обмен считается, только когда меняются местами два разных места списка; «обмен» элемента с самим собой (i совпало с j или с hi) список не меняет и в счёт не идёт.
Обсуждение
Вопросов пока нет.
Войдите, чтобы спросить.