2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Mountain Sort
Сообщение25.11.2019, 18:18 
Аватара пользователя


17/04/11
658
Ukraine
Загадка.
Цитата:
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» ничего не выдал.

 Профиль  
                  
 
 Re: Mountain Sort
Сообщение25.11.2019, 18:37 
Заслуженный участник


20/08/14
11058
Россия, Москва
Возможно, любой из этих.

 Профиль  
                  
 
 Re: Mountain Sort
Сообщение13.12.2019, 14:09 


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

 Профиль  
                  
 
 Re: Mountain Sort
Сообщение13.12.2019, 14:21 


10/04/12
704
beroal в сообщении #1427648 писал(а):
Тогда получаем алгоритм сортировки сложности $N$, что не возможно.

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

 Профиль  
                  
 
 Re: Mountain Sort
Сообщение13.12.2019, 14:48 


27/08/16
9426
mustitz в сообщении #1429983 писал(а):
Невозможно при условии использовать нее более чем $\mathcal O(1)$ памяти. Если использовать больше памяти, то можно быстрее.
Если используются только попарные сравнения, то нельзя.

 Профиль  
                  
 
 Re: Mountain Sort
Сообщение13.12.2019, 15:22 


10/04/12
704
realeugene в сообщении #1429986 писал(а):
Если используются только попарные сравнения, то нельзя.


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

 Профиль  
                  
 
 Re: Mountain Sort
Сообщение13.12.2019, 15:51 


27/08/16
9426
mustitz в сообщении #1429988 писал(а):
в оригинале рассматривался целочисленный массив,
Что не говорит ни о чём. В некоторых языках программирования диапазон представления целых чисел ограничен лишь объёмом доступной памяти. В таком случае, в качестве целого числа можно взять двоичное представление вообще произвольного объекта. Когда рассуждают про асимптотическую сложность сортировки, требуется конкретизировать, какие именно операции подсчитываются?

 Профиль  
                  
 
 Re: Mountain Sort
Сообщение15.12.2019, 20:54 
Заслуженный участник


15/05/05
3445
USA
Не это?
https://github.com/flatironinstitute/mountainsort

 Профиль  
                  
 
 Re: Mountain Sort
Сообщение15.12.2019, 21:06 
Аватара пользователя


17/04/11
658
Ukraine
Там импульсы, электроды. Вряд ли. :-)

 Профиль  
                  
 
 Re: Mountain Sort
Сообщение16.12.2019, 12:11 
Аватара пользователя


24/03/19
147
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).$

 Профиль  
                  
 
 Re: Mountain Sort
Сообщение16.12.2019, 15:07 
Аватара пользователя


17/04/11
658
Ukraine
SiberianSemion в сообщении #1430500 писал(а):
beroal, а откуда задача? Из сайта какого-нибудь?

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

 Профиль  
                  
 
 Re: Mountain Sort
Сообщение16.12.2019, 15:33 


27/08/16
9426
SiberianSemion в сообщении #1430500 писал(а):
вполне может означать, что массив исходно уже отсортирован "горным" образом, и надо лишь "досортировать" его в обычном порядке.
Да.

 Профиль  
                  
 
 Re: Mountain Sort
Сообщение16.12.2019, 16:03 
Аватара пользователя


24/03/19
147
realeugene, а! Вы писали о том же, а я в силу тугодумства и не понял. И вы наверняка заметили, что при нашей интерпретации там возникает нестыковка с примером, приведенным после условия задачи:
beroal в сообщении #1427648 писал(а):
For example, if the input array is A = [34, 12, 7, 43, 55, 97, 41, 28, 2, 62]

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group