Автор: PROGRAMMER_LAMER 13.11.2005 0:59
нужен алгоритм хора сортировки массива с двумя фиксироваными елементами
Автор: Altair 13.11.2005 1:30
Хоара может ? если да то вот:
http://forum.pascal.net.ru/index.php?showtopic=3065&view=findpost&p=27327
Автор: PROGRAMMER_LAMER 13.11.2005 1:33
Типа этого тока с двумя фиксированными точками
Автор: Altair 13.11.2005 1:38
Цитата
Типа этого тока с двумя фиксированными точками
Это как ? вся суть алгоритма заключается в фиксировании 1 точки, а разделении на 2 части...
Может я и не прав, (тогда рано или поздно меня поправят) но посмею заявить что сортировки Хоара с 2 точками нет!
Автор: Altair 13.11.2005 2:17
Как ты себе это представляешь ? Спроси у препода что он под этим понимает.
Вот иллюстрация алгоритма Хоара:
Цитата
Дано множество
{9,6,3,4,10,8,2,7}
Берем 9 в качестве базового элемента. Сравниваем 9 с противоположностоящим элементом, в данном случае это 7. 7 меньше, чем 9, следовательно элементы меняются местами.
{7,6,3,4,10,8,2,9}
Далее начинаем последовательно сравнивать элементы с 9, и менять их местами в зависимости от сравнения.
{7,6,3,4,10,8,2,9}
{7,6,3,4,10,8,2,9}
{7,6,3,4,10,8,2,9}
{7,6,3,4,9,8,2,10} - 9 и 10 меняем местами.
{7,6,3,4,8,9,2,10} - 9 и 8 меняем местами.
{7,6,3,4,8,2,9,10} - 2 и 9 меняем местами.
После такого перебрасывания элементов весь массив разбивается на два подмножетсва, разделенных элементом 9.
{7,6,3,4,8,2}
{10}
Далее по уже отработанному алгоритму сортируются эти подмножества. Подмножество из одного элемента естественно можно не сортировать. Выбираем в первом подмножестве базовый элемент 7.
{7,6,3,4,8,2}
{2,6,3,4,8,7} - меняем местами 2 и 7.
{2,6,3,4,8,7}
{2,6,3,4,8,7}
{2,6,3,4,8,7}
{2,6,3,4,7,8}- меняем местами 7 и 8
Получили снова два подмножества.
{2,6,3,4}
{8}
А дальше все происходит аналогично...
Если ты будешь использовать 2 фикс. элемента, как ты второй ьбудешь выбирать?
Опиши алгоритм, обоснавание и тогда можно бюудет написать программу... пока не представляю себе возможность выбора 2 элементов.
Автор: PROGRAMMER_LAMER 13.11.2005 16:13
два елемента беруться так n div 3 где n-длина массива
Автор: volvo 13.11.2005 16:26
To: PROGRAMMER_LAMER
n div 3 - это ОДИН элемент... Где второй, и как именно должна по-твоему происходить сортировка?
Автор: PROGRAMMER_LAMER 13.11.2005 16:30
n div 3 -1елемент 2*(n div 3) второй елемент
т е мы расбили наш массив на 3 подмассива щас их както методом хора отсортировать
Автор: volvo 13.11.2005 17:43
To: PROGRAMMER_LAMER
Это - НЕ алгоритм Хоара. Это называется "Троичное разбиение Бентли и Макклоу"
Автор: PROGRAMMER_LAMER 13.11.2005 18:26
А ЕСТЬ ЭТО У КОГО КТО МОЖЕТ АЛГОРИТМ ДАТЬ
Автор: Altair 13.11.2005 18:32
http://algolist.manual.ru/sort/mqs/fast_strings2.php
Цитата
Бентли и Макклоу [2] предложили троичное разбиение, основанное на следующем инварианте цикла: ...
http://www.3ka.mipt.ru/vlib/books/Programming/ComputerScience/FastStrings/fast_strings3.html
Цитата
Троичный алгоритм разбиения доставляет элегантную реализацию быстрой сортировки Хоара для составных ключей. Нижеследующий рекурсивный псевдокод сортирует последовательность s длины n, когда известно, что ее компоненты 1..d-1 равны друг другу; самый первый вызов – это, конечно sort(s, n, 1).
посмотри это...