IOM 2020, Блиц — Задача 65

The Blitz-contest of IOM-2020

Условие

Quicksort algorithm that sorts elements at lolo through hihi (inclusive) of an array AA can be expressed as

algorithm quicksort(A, lo, hi) isif lo < hi thenp := partition(A, lo, hi)quicksort(A, lo, p - 1)quicksort(A, p + 1, hi) algorithm partition(A, lo, hi) ispivot := A[hi]i := lofor j := lo to hi - 1 doif A[j] < pivot thenswap A[i] with A[j]i := i + 1swap A[i] with A[hi]return i\begin{array}{l}\texttt{algorithm quicksort(A, lo, hi) is}\\ \quad \texttt{if lo < hi then}\\ \qquad \texttt{p := partition(A, lo, hi)}\\ \qquad \texttt{quicksort(A, lo, p - 1)}\\ \qquad \texttt{quicksort(A, p + 1, hi)}\\ \texttt{ }\\ \texttt{algorithm partition(A, lo, hi) is}\\ \quad \texttt{pivot := A[hi]}\\ \quad \texttt{i := lo}\\ \quad \texttt{for j := lo to hi - 1 do}\\ \qquad \texttt{if A[j] < pivot then}\\ \qquad\quad \texttt{swap A[i] with A[j]}\\ \qquad\quad \texttt{i := i + 1}\\ \quad \texttt{swap A[i] with A[hi]}\\ \quad \texttt{return i}\end{array}

The letters of the word OLYMPIAD are placed in a random order. How many comparisons in the partition algorithm does the quicksort algorithm need in the worst case to bring the letters back into the correct order?

Отговори

Решение

Внимание: Непълно решение

The source contains only the answer key, no worked solution.

Оригинал в Архива: iom-2020-blitz-tasks.pdf · официални решения: iom-2020-blitz-answers.pdf