|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Stanislav Shwartsman 2:400/520 27 Feb 2002 21:56:08
To : Paul Yanchenko
Subject : Сортировка списка слов по алфавиту
--------------------------------------------------------------------------------
27 Feb 02 11:04, you wrote to Max Litvinov:
PY> Берешь любой алгоритм сортировки. В любом алгоритме сортировки тебе
PY> нужно уметь переставлять элементы местами. Hу вот и все, осталось
PY> только сравнивать строки так, чтобы строка, которая по алфавиту должна
PY> быть раньше была "меньше", чем строка, которая по алфавиту должна быть
PY> позже. Любой паскаль так умеет ( if s1<s2 then ... )
Любой "простой" алгоритм сортировки даст слишком большую сложность.
Да, сортировка это O(NlogN), где N - количество слов. Hо сравнение
двух слов между собой это тоже O(m), где m - средняя длина слова.
Для решения этой проблемы есть такая структура данных - Trie. Быстрая
сортировка - засунуть весь словарь в Trie, а потом вынуть оттуда
in-order.
Кратко Trie это дерево, только не двоичное, K+1 - ичное, где К -
количество букв в алфавите.
S
/ | \
a b c
| | | \
0 0 0 c
|
0
Вот так например выглядит структура Trie с засунутыми в него словами
{ a, b, c, cc }.
E-mail: gate@fidonet.org.il
Voice Phones: 972-4-8330554 (home), 972-5-4481073 (cell)
Bye !
Stanislav (AKA Night's Man) [Team Technion]
---
* Origin: Gate From Another World ... From Haifa, Israel (2:400/520)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
