ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Ilya Teterin                         2:5020/400     08 Apr 2003  20:16:26
 To : Val Krigan
 Subject : Re: Сортировка
 -------------------------------------------------------------------------------- 
 

 Tue Apr 08 2003 19:37, Val Krigan wrote to Ilya Teterin:
 
  VK> Как у тебя массив nodes получился отсортированным после добавления
  VK> элементов по адресу основанному на хеш-функции? Уж не пердпологаешь ли
  VK> ты, что она сохраняет порядок следования и
  VK>     если е1>e2, то
  VK>     hash_func(e1)>hash_func(e2)
  VK> ?
 
 Как-то ты невнимательно читал комментарии к моему первому исходнику... Hа бис:
 
 --------
 Комментарии: функция hash_func выбирается в зависимости от конкретной задачи,
 должна возвращать значение [0..hash_space-1] и удовлетворять условию a1<a2 =>
 hash_func(a1)<=hash_func(a2). В зависимости от того, насколько хорошо ее
 удастся выбрать и размера hash_space, сложность сортировки изменяется от
 qsort-овской (наихудший случай -  все элементы попали в один hash_node) до
 O(n) (наилучший случай - каждый hash_node содержит не более одного элемента).
 --------
 
  VK> Если да, то пжалста примерчик для целочисленной ф-ции от real переменно.
 
 И она была в исходике... Ты его вообще читал, или только обнаружил непохожесть
 на свою идею, и сразу закричал "ужас"? :)
 
 int hash_func(double arg){
         return int((arg-min)/(max-min)*hash_space);
 }
 
 Это - для равномерного распределения, min и max - минимальное и максимальное
 значение входных данных соответственно. Для другого распределения оптимальный
 вид функции будет другим. Обо всем этом я уже говорил...
 
 Идеально было бы, если бы можно было легко построить функцию, которая по
 значению элемента сразу выдавала бы его позицию в отсортированном массиве, но
 я не знаю такого алгоритма сложности меньше O(n), и поэтому приходится
 пользоваться подходящим для конкретной задачи приближением, когда часть
 различных элементов попадает на одну позицию, а часть позиций остается
 незанятыми, а потом приводить все в "правильный" порядок.
 
  >> Забыл еще одно условие - при отсутствии повторений среди входных данных.
  VK> Hе спасает :))
 
 Простите, от чего не спасает? :)
 
 --- ifmail v.2.15dev4
  * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор