Метод сортировки файлов многофазным слиянием
Мог бы мне кто-то доступно объяснить как работает этот метод и как его реализовать? Только плиз проще!:???:
Есть один мега адресок, вот он:
google.com
Забиваешь туда МНОГОФАЗНОЕ СЛИЯНИЕ, и получаешь кое-какие ссылки.
Например вот эту http://program.rin.ru/razdel/html/788.html
ну и т.д. и т.п.
Есть один мега адресок, вот он:
google.com
Забиваешь туда МНОГОФАЗНОЕ СЛИЯНИЕ, и получаешь кое-какие ссылки.
Например вот эту http://program.rin.ru/razdel/html/788.html
ну и т.д. и т.п.
Слушай, таких ссылок я за неделю открыл штук 50
Я по-моему просил объяснить, как ты ее [censored] сортировку понимаешь. Ну так как, мысли есть? X)- X)- X)-
Слушай, таких ссылок я за неделю открыл штук 50
Я по-моему просил объяснить, как ты ее [censored] сортировку понимаешь. Ну так как, мысли есть? X)- X)- X)-
Открываем Кнута (Исскуство программирования т.3 Сортировка и поиск)и читаем:
Алгоритм многофазного слияния:
а1. Распределить начальные серии попеременно на ленты Т1 и Т2
а2. Слить серии с лент Т1 и Т2 на Т3, остановиться если на Т3 содержиться только одна серия
а3. Скопировать половину серий Т3 на Т2
а4. Слить серии с лент Т1 и Т3 на Т2, остановиться если на Т2 всего одна серия
а5. Скопировать половину серий с Т2 на Т1. Вернуться к шагу а2.
Успехов.
Слушай, таких ссылок я за неделю открыл штук 50
Я по-моему просил объяснить, как ты ее [censored] сортировку понимаешь. Ну так как, мысли есть? X)- X)- X)-
Ок, мое понимание этого дела такое:
У нас есть несколько упорядоченных списков (серий, лент, кому как удобно :) их то мы и записываем в один упорядоченный результат.
С Кнутовским алгоритмом к сожалению на данный момент не знаком. Для меня идея многофазного слияния это просто выбирание неимениших значений из списков и переписывание их в результирующий файл (список).
Вот. Могу и шибаться. Практически никогда потребности в реализации этого не было.
Ок, мое понимание этого дела такое:
У нас есть несколько упорядоченных списков (серий, лент, кому как удобно :) их то мы и записываем в один упорядоченный результат.
С Кнутовским алгоритмом к сожалению на данный момент не знаком. Для меня идея многофазного слияния это просто выбирание неимениших значений из списков и переписывание их в результирующий файл (список).
Вот. Могу и шибаться. Практически никогда потребности в реализации этого не было.
Ну вобщем суть ты правильно уловил.
Есть серия значений. Очень большая. Нам нужно ее упорядочить. Мы разбиваем ее на две части и последовательно идем по обоим подсериям сравнивая один эл-т подсерии с другим. в промежуточный результат записываем сначала (скажем меньшее потом большее занчение) получаем таким образом промежуточную серию, состоящую из уже упорядоченных кусочков. Опять делим на две подсерии и опять сливаем и т.д.
Открываем Кнута (Исскуство программирования т.3 Сортировка и поиск)и читаем:
Алгоритм многофазного слияния:
а1. Распределить начальные серии попеременно на ленты Т1 и Т2
а2. Слить серии с лент Т1 и Т2 на Т3, остановиться если на Т3 содержиться только одна серия
а3. Скопировать половину серий Т3 на Т2
а4. Слить серии с лент Т1 и Т3 на Т2, остановиться если на Т2 всего одна серия
а5. Скопировать половину серий с Т2 на Т1. Вернуться к шагу а2.
Успехов.
Ладно, мне надоело повторять одно и тоже. Скажу по-другому:
Я читаю Вирта, Кнута, но ни х__ не понимаю (вернее каша в голове) если хочешь помочь по-настоящему, напиши как своими словами как ты понимаешь это все сам :devil: :devil: :devil:
Мог бы мне кто-то доступно объяснить как работает этот метод и как его реализовать? Только плиз проще!:???:
Заходишь http://foxweb.net.ru/files/, вводишь "многофазное слияние" и качаешь...
Ну вобщем суть ты правильно уловил.
Есть серия значений. Очень большая. Нам нужно ее упорядочить. Мы разбиваем ее на две части и последовательно идем по обоим подсериям сравнивая один эл-т подсерии с другим. в промежуточный результат записываем сначала (скажем меньшее потом большее занчение) получаем таким образом промежуточную серию, состоящую из уже упорядоченных кусочков. Опять делим на две подсерии и опять сливаем и т.д.
А я вот интересуюсь ???
Ето поолучается рекурсия (я так понял). Ми ее продолжаем пока в серии не останется один елемент. Я правильно понял ?
Если да, то долговато. Но можно маленькие сесии на определенной глубине рекурсии и по другому сортировать (чтоб в глубь дальше не идти).
А я вот интересуюсь ???
Ето поолучается рекурсия (я так понял). Ми ее продолжаем пока в серии не останется один елемент. Я правильно понял ?
Если да, то долговато. Но можно маленькие сесии на определенной глубине рекурсии и по другому сортировать (чтоб в глубь дальше не идти).
Почитать об этом методе можно очень подробно ЗДЕСЬ: http://citforum.ru/programming/theory/sorting/sorting1.shtml