Mountain Sort

[beroal]

Загадка.

Цитата:

Implement Mountain Sort, an algorithm with a time complexity of $\Theta(N)$ that sorts the integer numbers stored in an array in the following way:

• The first $N/2$ lowest numbers are stored from smallest to largest in the left half of the array
• The next $N/2$ numbers are stored from largest to smallest in the right half of the array

For example, if the input array is A = [34, 12, 7, 43, 55, 97, 41, 28, 2, 62], the sorted array should be [2, 7, 12, 28, 34, 97, 62, 55, 43, 41]. You may assume that the number of elements in the array is even.

Цитата:

Реализуйте «горную сортировку», алгоритм сложности $\Theta(N)$, который сортирует целые числа, находящиеся в массиве, следующим образом:

• первые $N/2$ наименьших чисел должны располагаться от меньших к большим в левой половине массива;
• следующие $N/2$ чисел должны располагаться от больших к меньшим в правой половине массива.

Например, если входной массив A = [34, 12, 7, 43, 55, 97, 41, 28, 2, 62], отсортированный массив должны быть [2, 7, 12, 28, 34, 97, 62, 55, 43, 41]. Исходите из того, что количество элементов массива чётно.

Если я правильно понял спецификацию этого «Mountain Sort», обычную сортировку можно свести к «Mountain Sort»: отсортировать и перевернуть правую половину массива. Тогда получаем алгоритм сортировки сложности $N$, что не возможно. Веб по поводу «Mountain Sort» ничего не выдал.

[Dmitriy40]

Возможно, любой из этих.

[realeugene]

beroal в сообщении #1427648 писал(а):

Тогда получаем алгоритм сортировки сложности $N$, что не возможно.

Две сортированные последовательности длиной $N/2$ легко слить в одну сортированную последовательность длиной $N$ за $O(N)$. Так что, да, постановщики задачи о чём-то умалчивают. А "целые числа" не обязаны иметь определённую максимальную ширину.

[mustitz]

beroal в сообщении #1427648 писал(а):

Тогда получаем алгоритм сортировки сложности $N$, что не возможно.

Невозможно при условии использовать нее более чем $\mathcal O(1)$ памяти. Если использовать больше памяти, то можно быстрее.

[realeugene]

mustitz в сообщении #1429983 писал(а):

Невозможно при условии использовать нее более чем $\mathcal O(1)$ памяти. Если использовать больше памяти, то можно быстрее.

Если используются только попарные сравнения, то нельзя.

[mustitz]

realeugene в сообщении #1429986 писал(а):

Если используются только попарные сравнения, то нельзя.

Да, просто в оригинале рассматривался целочисленный массив, поэтому моё высказывание относилось к этому случаю, а не к сортировке вообще.

[realeugene]

mustitz в сообщении #1429988 писал(а):

в оригинале рассматривался целочисленный массив,

Что не говорит ни о чём. В некоторых языках программирования диапазон представления целых чисел ограничен лишь объёмом доступной памяти. В таком случае, в качестве целого числа можно взять двоичное представление вообще произвольного объекта. Когда рассуждают про асимптотическую сложность сортировки, требуется конкретизировать, какие именно операции подсчитываются?

[Yuri Gendelman]

Не это?
https://github.com/flatironinstitute/mountainsort

[beroal]

Там импульсы, электроды. Вряд ли.

[SiberianSemion]

beroal, а откуда задача? Из сайта какого-нибудь? Мне почему-то мерещится эффект "испорченного телефона" (я не про вас, а про авторов задачи). Я не специалист по английскому, но вот это

beroal в сообщении #1427648 писал(а):

Implement Mountain Sort, an algorithm with a time complexity of $\Theta(N)$ that sorts the integer numbers stored in an array in the following way:
The first $N/2$ lowest numbers are stored from smallest to largest in the left half of the array
The next $N/2$ numbers are stored from largest to smallest in the right half of the array

вполне может означать, что массив исходно уже отсортирован "горным" образом, и надо лишь "досортировать" его в обычном порядке. А с примером авторы вполне могли допустить ошибку.
При такой интерпретации очевидно, почему присутствует оценка вида $\Theta(N).$

[beroal]

SiberianSemion в сообщении #1430500 писал(а):

beroal, а откуда задача? Из сайта какого-нибудь?

Из личной переписки. Задача в вузе.

[realeugene]

SiberianSemion в сообщении #1430500 писал(а):

вполне может означать, что массив исходно уже отсортирован "горным" образом, и надо лишь "досортировать" его в обычном порядке.

Да.

[SiberianSemion]

realeugene, а! Вы писали о том же, а я в силу тугодумства и не понял. И вы наверняка заметили, что при нашей интерпретации там возникает нестыковка с примером, приведенным после условия задачи:

beroal в сообщении #1427648 писал(а):

For example, if the input array is A = [34, 12, 7, 43, 55, 97, 41, 28, 2, 62]

тут половинки не сортированы. Я так предполагаю, исходно задача была придумана одним человеком, а пример был добавлен позже, "от себя" $-$ другим.