Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия, Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
Дано: массив длиной .место каждого члена равно меньше от того места где тот член должен быть в сортированном массиве. Требуется предложить алгоритм который справляется с задачей сортировки в .
Кто может дать подсказку пути решения?
Null
Re: Создать алгоритм сортировки
24.11.2010, 00:09
Можно сделать пирамидальную сортировку с пирамидой размера
ИСН
Re: Создать алгоритм сортировки
24.11.2010, 00:11
Тупо берём k верхних. (Где-то среди них настоящий верхний.) Их честно сортируем. Один выставляем. Ещё один берём и вставляем...
Null
Re: Создать алгоритм сортировки
24.11.2010, 12:59
Вставка . Или в чем хранить предлагаете.
Dandan
Re: Создать алгоритм сортировки
24.11.2010, 16:24
вставка в отсортированный кусок из элементов будет происходить за
Ну тогда он не от сортированный получается а как я сказал пирамида(двоичная куча)
Dandan
Re: Создать алгоритм сортировки
24.11.2010, 17:45
в начале мы создаем кучу из верхних k элементов. На каждом шаге мы будем извлекать максимальный элемент из кучи и вставлять новый. В конце из извелеченных максимальных у нас получится массив, а не куча.
Null
Re: Создать алгоритм сортировки
24.11.2010, 17:51
Мы говорим про кусок из k элементов он не отсортированный, он куча.