|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Kadatch 2:5020/400 05 Jun 2001 12:22:54
To : All
Subject : Re: сортировка динамического списка
--------------------------------------------------------------------------------
> IZ> Hарод, поделитесь сабжем. Hе дайте погибнуть заочнику :)))
> IZ> В книгах не нашёл, а своим умом не могу дойти, не хватает
> IZ> информации, да и материал этот не начитывали.
> IZ> Сабж нужен на паскале.
> а cколко я помню cпcки только вcтавкой cоpтиpовать можно.
Hу-ну... А если построить сбалансированное дерево поиска (AVL, 2-3,
red-black, и т.д)
и затем обойти?
А как же классическая сортировка слиянием -- одна из лучших?
Рассмотрим неотсортированный список длины N как последовательность
из N подсписков длины 1. Подсписок, содержащий ровно один элемент,
отсортирован по определению.
Допустим, что на некотором шаге имеется последовательность из K
отсортированных
подсписков длины M (кроме последнего, который может быть короче).
Возьмем два первых отсортированных подсписка и сольем их в один список длины
2M
сравнением первых элементов подсписков и удалением наибольшего, который
необходимо
добавить в конец порождаемого списка.
Применив слияние K/2 раз, получим последовательность из K/2 отсортированных
подсписков длины 2М.
Итак, на каждом шаге количество подсписков уменьшается вдвое, а их длина
удваивается,
поэтому за log_2 N итераций N отсортированных подсписков длины один
превращаются,
превращаются, ... -- нет, не в элегантные шорты, а в последовательность,
содержащую ровно
один отсортированный подсписок длины N, который и нужно было построить.
Поскольку
сложность каждого шага равна O(N), то сложность сортировки слиянием равна
O(N log N),
т.е. она асимптотически оптимальна.
Построение эффективной реализации, которая не требует дополнительной памяти
и обходится
односвязными списками, а также пытается найти начало второго подсписка
пропуском M элементов,
предоставляется в качестве упражнения.
Удачи,
АК
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
