|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ilya Teterin 2:5020/400 05 Apr 2003 08:46:33
To : Artur Mogozov
Subject : Сортировка
--------------------------------------------------------------------------------
Sat Apr 05 2003 08:57, Artur Mogozov wrote to Ilya Teterin:
AM> Hу вот, например, 7.3 и 7.4 - преобразуем в целые, это 7 и 7. Две
AM> семерки. Hу что ж, запишем в массив. При выводе выводим две семерки. Hо
AM> это не верно! Во- -первых, у нас было 2 разных числа, а мы вывели 2
AM> одинаковых, во-вторых ни одно из них не равно 7...
Поэтому в массив не надо записывать две семерки :) Hадо записывать цепочку,
содержащую 7.3 и 7.4, а на начало цепочки будет указывать ячейка массива с
индексом 7. Перед выдачей результата элементы цепочки надо отсортировать, уже
обычным алгоритмом.
Вычислительная сложность такого алгоритма, понятно, будет выше O(n), но при не
очень противном распределении и правильном выборе преобразования float -> int
близка к O(n).
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
