2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Создать алгоритм сортировки
Сообщение23.11.2010, 23:33 
Аватара пользователя


24/09/09
45
Jer
Дано:
массив длиной $n$ .место каждого члена равно меньше $k$ от того места где тот член должен быть в сортированном массиве.
Требуется предложить алгоритм который справляется с задачей сортировки в $O(n logk)$.

Кто может дать подсказку пути решения?

 Профиль  
                  
 
 Re: Создать алгоритм сортировки
Сообщение24.11.2010, 00:09 
Заслуженный участник


12/08/10
1645
Можно сделать пирамидальную сортировку с пирамидой размера $3k$

 Профиль  
                  
 
 Re: Создать алгоритм сортировки
Сообщение24.11.2010, 00:11 
Заслуженный участник
Аватара пользователя


18/05/06
13437
с Территории
Тупо берём k верхних. (Где-то среди них настоящий верхний.) Их честно сортируем. Один выставляем. Ещё один берём и вставляем...

 Профиль  
                  
 
 Re: Создать алгоритм сортировки
Сообщение24.11.2010, 12:59 
Заслуженный участник


12/08/10
1645
Вставка $O(k)$. Или в чем хранить предлагаете.

 Профиль  
                  
 
 Re: Создать алгоритм сортировки
Сообщение24.11.2010, 16:24 


24/03/07
321
вставка в отсортированный кусок из $k$ элементов будет происходить за $O(logk)$

 Профиль  
                  
 
 Re: Создать алгоритм сортировки
Сообщение24.11.2010, 17:09 
Заслуженный участник


12/08/10
1645
Как?

 Профиль  
                  
 
 Re: Создать алгоритм сортировки
Сообщение24.11.2010, 17:30 


24/03/07
321
с помощью сортирующего дерева http://ru.wikipedia.org/wiki/%D0%A1%D0% ... 0%B2%D0%BE. Которое, кстати, как раз и используется в пирамидальной сортировке.

 Профиль  
                  
 
 Re: Создать алгоритм сортировки
Сообщение24.11.2010, 17:37 
Заслуженный участник


12/08/10
1645
Ну тогда он не от сортированный получается а как я сказал пирамида(двоичная куча)

 Профиль  
                  
 
 Re: Создать алгоритм сортировки
Сообщение24.11.2010, 17:45 


24/03/07
321
в начале мы создаем кучу из верхних k элементов. На каждом шаге мы будем извлекать максимальный элемент из кучи и вставлять новый. В конце из извелеченных максимальных у нас получится массив, а не куча.

 Профиль  
                  
 
 Re: Создать алгоритм сортировки
Сообщение24.11.2010, 17:51 
Заслуженный участник


12/08/10
1645
Мы говорим про кусок из k элементов он не отсортированный, он куча.

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

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



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

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


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

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