LINUX.ORG.RU

Алгоритм сортировки - помогите убогому :(


0

0

Нужен алгоритм внешней сортировки простым слиянием. Если размер массива 2^n - фигня вопрос, дело десяти минут. А если произвольный размер массива? Вторую неделю придумать не могу, башка дымиться

anonymous

Re: Алгоритм сортировки - помогите убогому :(

Постарайся развернутее описать свой вопрос. Я 2 минуты перечитывал, так нечего не понял.

mutable ()

Re: Алгоритм сортировки - помогите убогому :(

Алгоритм. Внешней сортировки простым слиянием. Сортировка есть такая - простым слиянием, внешняя. Элементарно реализуется если размер сортируемого массива данных 2^n. Могу описать сам алгоритм...

anonymous ()

Re: Алгоритм сортировки - помогите убогому :(

anonymous (*) (05.06.2006 16:48:03):

> Сортировка есть такая - простым слиянием, внешняя.

Хоть на анлийском бы написАл...

У меня, например, ничего не шевельнулос... Merge sorting, как я понимаю, не то?

А "внешняя" -- "external", или как?

Die-Hard ★★★★★ ()

Re: Алгоритм сортировки - помогите убогому :(

> если произвольный размер массива?

делишь пополам, если нечётное -- почти напополам, если единица -- уже отсортировано. сортируешь половинки рекурсивно, сливаешь взад.

в чём проблема-то?

anonymous ()

Re: Алгоритм сортировки - помогите убогому :(

2bbk123:

> http://iclub.nsu.ru/~andy/Lectures/ExternalSearch.html

В Высшей Степени Научно! Если ты разрабатываешь драйве для файлухи, или СУБД на raw девайсах оно, конечно, не совсем глупо, хотя и тривиально...

На практике же ты имеешь дело с кэшированием/буферизацией с последующим рескедьюлингом как на уровне операционки, так и на уровне контроллеров, а все 2*P девайсов объединены в (страйпнутый) райд.

Имеется много реализаций split'n'merge для случаев, когда данные не влезают в память. Собственно, почти все реализации сортировки данных, не влазающих в память, основанны на split'n'merge.

По моим наблюдениям,

1. Оптимальнее всего сливать не P ветвей, а 2. Мало того, при P>2 на достаточных объемах данных (начиная уже с сотен гигабайт) получаются проблемы, особенно под RaiserFS.

2. Буферизация необходима, но сортировку лучше отделять от буферизации.

Die-Hard ★★★★★ ()

Re: Алгоритм сортировки - помогите убогому :(

Насчет оригинального вопроса:

Не понял проблему...

Если последняя запись короче M, то и Бог с ним, пусть будет короче M. Хоть бы и 1 -- она, кстати, уже и отсотрирована будет...

Если вдруг все влезло, игнорируешь оставшиеся свободные устройства.

Если на каком-либо устройстве записей больше нет, исключаешь его из слияния.

Die-Hard ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.