2014 dxdy logo

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

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




 
 Создать алгоритм сортировки
Сообщение23.11.2010, 23:33 
Аватара пользователя
Дано:
массив длиной $n$ .место каждого члена равно меньше $k$ от того места где тот член должен быть в сортированном массиве.
Требуется предложить алгоритм который справляется с задачей сортировки в $O(n logk)$.

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

 
 
 
 Re: Создать алгоритм сортировки
Сообщение24.11.2010, 00:09 
Можно сделать пирамидальную сортировку с пирамидой размера $3k$

 
 
 
 Re: Создать алгоритм сортировки
Сообщение24.11.2010, 00:11 
Аватара пользователя
Тупо берём k верхних. (Где-то среди них настоящий верхний.) Их честно сортируем. Один выставляем. Ещё один берём и вставляем...

 
 
 
 Re: Создать алгоритм сортировки
Сообщение24.11.2010, 12:59 
Вставка $O(k)$. Или в чем хранить предлагаете.

 
 
 
 Re: Создать алгоритм сортировки
Сообщение24.11.2010, 16:24 
вставка в отсортированный кусок из $k$ элементов будет происходить за $O(logk)$

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

 
 
 
 Re: Создать алгоритм сортировки
Сообщение24.11.2010, 17:30 
с помощью сортирующего дерева http://ru.wikipedia.org/wiki/%D0%A1%D0% ... 0%B2%D0%BE. Которое, кстати, как раз и используется в пирамидальной сортировке.

 
 
 
 Re: Создать алгоритм сортировки
Сообщение24.11.2010, 17:37 
Ну тогда он не от сортированный получается а как я сказал пирамида(двоичная куча)

 
 
 
 Re: Создать алгоритм сортировки
Сообщение24.11.2010, 17:45 
в начале мы создаем кучу из верхних k элементов. На каждом шаге мы будем извлекать максимальный элемент из кучи и вставлять новый. В конце из извелеченных максимальных у нас получится массив, а не куча.

 
 
 
 Re: Создать алгоритм сортировки
Сообщение24.11.2010, 17:51 
Мы говорим про кусок из k элементов он не отсортированный, он куча.

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group