алгоритм поиска - метод "перемешивание"

← →
Дева © (2006-01-15 14:19) [0]

Здравствуйте, мастера. Не могу найти нигде алгоритм поиска - метод перемешивание. Задание для курсовой. Ни у Кнута, ни у Вирта нету такого метода вообще! Или я такая невнимательная, или...
Может кто знаком с ним? Подскажите, если знаете

← →
Cash © (2006-01-15 15:26) [1]

Что то я вобще не припомню такого метода. 8)
Конкретизируй вопрос: какова задача поиска, над какими структурами
производится, и по какому предмету курсовая.

← →
Zeqfreed © (2006-01-15 15:51) [2]

Дева © (15.01.06 14:19)
Поиск в гугле подтвердил мое предположение, что сортировка перемешиванием так же известна как «шейкер-сортировка», «сортировка коктейлем» и «двунаправленная сортировка пузырьком». Теперь все в Ваших руках :)

← →
з. танька (2006-01-15 16:18) [3]

> «двунаправленная сортировка пузырьком».

да, куда уж Кнуту и Вирту до такого :)

← →
VirEx © (2006-01-15 16:29) [4]

пузырьки, коктейли, шейкеры... даёшь свободу мысли! даёшь высокий градус! ура товарищи!

← →
Cash © (2006-01-15 16:44) [5]

А ну если дама оговорилась и это всетаки сортировка, то на:
Type TStatPrm = record trmit: integer; Check: integer; end; Procedure ShakerSort(var amas: array of integer;var Prm: TStatPrm); var i: integer; l,h,k: integer; begin l:=Low(amas); h:=High(amas); k:=h; Prm.check:=0; Prm.trmit:=0; repeat for i:=h downto l+1 do begin if amas[i] < amas[i-1] then begin TransMit(amas[i],amas[i-1]); Prm.trmit:=Prm.trmit+1; k:=i; end; Prm.check:=Prm.check+1; end; l:=k; for i:=l to h-1 do begin if amas[i] > amas[i+1] then begin TransMit(amas[i],amas[i+1]); Prm.trmit:=Prm.trmit+1; k:=i; end; Prm.check:=Prm.check+1; end; h:=k; until l>=h; end;

← →
Дева © (2006-01-15 17:58) [6]

Господа, я не оговорилась. Сама бы рада. Тем более, что с сортировкой я разобралась.
У меня есть методичка по предмету (кстати, отвечаю - курс "Структуры и алгоритмы обработки данных"). В конце методички список методов для курсовой.
Вот:
Методы доступа
//не буду подробно
Методы хэширования
//тоже
//В любом случае - эта графа отдельно, значит метод "перемешивание"
//к хэшированию не относиться
Методы поиска в индексе
1. Последовательный просмотр.
2. Блочный поиск
3. Двоичный поиск
4. Поиск по двоичному дереву
5. Сбалансированное индексное дерево с последовательным просмотром узлов
6. Сбалансированное индексное дерево с блочным поиском в узлах
7. Сбалансированное индексное дерево с двоичным поиском в узлах
8. Операции с набором указателей
9. Буферы повторного поиска
10. Несбалансированные деревья
11. Адресация с помощью местоположения элемента
12. Алгоритмическое индексирование
13. Перемешивание (вот оно мое)
Методы сортировки (внутренней)
//тоже подробно останавливаться не буду - не это сейчас нужно

Даже половины я ни у Кнута, ни у Вирта не нахожу, если честно! :(
А о сортировке и хэшировании я вообще молчу! Брррррр. До них дело еще не дошло......

← →
palva © (2006-01-15 18:23) [7]

13. Перемешивание (вот оно мое)
Скорее всего, это плохой перевод слова хэширование. Это когда запись стараются положить в массив по индексу, равному некоторой хэш-функции ключа этой записи.

← →
Zeqfreed © (2006-01-15 18:30) [8]

palva © (15.01.06 18:23) [7]
Видимо [2] получилось не очень убедительно? Я повторюсь, что проверил свою догадку в гугле, а потому считаю свою точку зрения достаточно конкурентноспособной. :)
Вот линк, приведший меня к вышеизложенному умозаключению: http://ru.wikipedia.org/wiki/Алгоритм_сортировки

← →
palva © (2006-01-15 18:53) [9]

Я просто знаю, что хэширование, рандомизация, перемешивание - это синонимы
http://www.telesys.ru/wwwboards/dsp/31/messages/11190.shtml
В очень древних книгах 60-х годов так и писали "перемешивание". Потом появилась рандомизация.

Хэширование вопрос принципиальный, и он должен быть в учебной программе как один из методов построения индексов. А вот двунаправленный пузырек это очень большая частность.

Но я ни на чем не настаиваю.

← →
Zeqfreed © (2006-01-15 19:18) [10]

palva © (15.01.06 18:53) [9]
Ясно. Я с такими книгами не знаком — поколение пепси, так сказать :)
Ну и, насколько я понимаю, в [6] хэширование идет совершенно другим пунктом. Но я, разумеется, тоже ни на чем не настаиваю :)

Дева © (15.01.06 17:58) [6]:
Значит САОДу учамся. Нам поиск давли только бинарый, в упорядоченном
масивы. А все остальные методы из ваших пунктов - по главам.
(Бин. деревья -> поиск в бин. деревьях, и т. д.)
Ну а в самой методичке что нибудь написано по этому методу, хоть к какой
отрасли поиска он относится.

[7] и [8] Почему вы невнимательно читаете [6]
Я же там написала весь список. Хэширование и сортировка идут отдельно. И потом, метод поиска - перемешивание мне давала преподавательница сама лично. Значит вариант "неправильно перевели" отпадает! Я думаю она знала, о чем говорит.
2 Cash [1]
Структура:
хранение во внешней памяти, индексно-произвольный метод, B-tree

Дева © (16.01.06 09:23) [12]:
Ну..., девушка, под структурой я имел ввиду на выбор:
"Деревья (они тоже разные), списки, масивы (только упорядоченные),хеш таблицы".

... , B-tree ...
Если так, как мне показалось, и это поиск в деревьях, то...
По моему дерево должно быть индексно упоядоченным
(слева от головы элементы с меньшим индексом, с права - с большим.
Для каждого из поддеревьев этого дерева)

Тогда все дело заключается в одной рекурсивной функции:
Type PMyTreeNode = ^TMyTreeNode; TMyTreeNode = record Index: integer; Left: PMyTreeNode; Right: PMyTreeNode; end; function Find(Head: PMyTreeNode; const needed: integer): PMyTreeNode; begin Result := Nil; if Head = nil then exit; if Head^.Index <> needed then begin if (needed-Head^.Index) then Result := Find(Head^.Right,needed) else Result := Find(Head^.Left,needed); end else Result := Head; end;

Дева © (16.01.06 09:23) [12]:
О ужас..., до меня дошло, поиск по Б-дереву. Все, что угодно..., только не
Б-деревья, ненавижу! (хоть я их и сдавал)
Тут я кодом не помогу.... :(
Зато помогу ссылкой:
http://algolist.manual.ru/
А по конкретнее:
http://algolist.manual.ru/ds/s_btr.php

Поставь алголист себе на заметку, очень полезный сайт,
поможет в будущем.

алгоритм поиска - метод "перемешивание" Найти похожие ветки