Внешняя многофазная сортировка

Аватара пользователя
Dmitriy
Сообщения: 12
Зарегистрирован: 02 фев 2012, 11:42

Внешняя многофазная сортировка

Сообщение Dmitriy » 12 апр 2012, 21:27

Здравствуйте! Такой вопрос на засыпку)
Существует такая многофазная сортировка!
Алгоритм понятен поверхностно, но сделать надо поэтому откапал материал
http://www.scribd.com/doc/50338190/67/% ... 0%BA%D0%B0

Сделал 1 часть распределение на два файла с сортировкой!
Но как делать 2 часть вообще не понимаю!
Помогите либо примером? Либо алгоритмом! Очень прошу)
Заранее спасибо!

Внимательно проверяем название :-):. Vlad

Аватара пользователя
Andrey
Администратор
Администратор
Сообщения: 2345
Зарегистрирован: 02 фев 2012, 11:42
Откуда: Воронеж
Контактная информация:

Re: Внешняя многофазныя сортировка

Сообщение Andrey » 12 апр 2012, 21:30

Если я правильно понял, то алгоритм на псевдокоде там есть и нужно описать его на delphi?

Аватара пользователя
Dmitriy
Сообщения: 12
Зарегистрирован: 02 фев 2012, 11:42

Re: Внешняя многофазныя сортировка

Сообщение Dmitriy » 12 апр 2012, 21:36

Это конечно, хорошо, но лучше чтобы объяснили, если можно) как мы будем сливать два файла к примеру! Ведь когда мы используем Внешнюю сортировку то память забита и нельзя использовать массив для сортировки двух отрезков из файла и записи в другой!

Аватара пользователя
Andrey
Администратор
Администратор
Сообщения: 2345
Зарегистрирован: 02 фев 2012, 11:42
Откуда: Воронеж
Контактная информация:

Re: Внешняя многофазныя сортировка

Сообщение Andrey » 12 апр 2012, 21:38

Это всё до завтра надо? Просто немного поздновато.

Аватара пользователя
Dmitriy
Сообщения: 12
Зарегистрирован: 02 фев 2012, 11:42

Re: Внешняя многофазныя сортировка

Сообщение Dmitriy » 12 апр 2012, 21:40

ну можно на словах, я не много не понимаю алгоритм! Поэтому и застопорился! Если вас не затруднит! Буду оч благодарен)

Аватара пользователя
Andrey
Администратор
Администратор
Сообщения: 2345
Зарегистрирован: 02 фев 2012, 11:42
Откуда: Воронеж
Контактная информация:

Re: Внешняя многофазныя сортировка

Сообщение Andrey » 12 апр 2012, 21:50

Дело в том что я с этим алгоритмом не сталкивался. Слышал о нём, но не более того и чтобы понять нужно внимательно прочитать и только потом могу написать более простыми словами. Но я не уложусь в оставшиеся 10 минут, затем до завтрашнего вечера возможности ответить не будет. Поэтому если это нужно не завтра, то потом напишу, если завтра, то к сожалению не смогу.

Аватара пользователя
Dmitriy
Сообщения: 12
Зарегистрирован: 02 фев 2012, 11:42

Re: Внешняя многофазныя сортировка

Сообщение Dmitriy » 12 апр 2012, 21:53

Спасибо и на этом) Завтра тогда жду вашего ответа с нетерпением)

Аватара пользователя
Andrey
Администратор
Администратор
Сообщения: 2345
Зарегистрирован: 02 фев 2012, 11:42
Откуда: Воронеж
Контактная информация:

Re: Внешняя многофазныя сортировка

Сообщение Andrey » 12 апр 2012, 21:54

Если часов в 6 вечера ответа не будет напомните.

Аватара пользователя
Dmitriy
Сообщения: 12
Зарегистрирован: 02 фев 2012, 11:42

Re: Внешняя многофазныя сортировка

Сообщение Dmitriy » 14 апр 2012, 19:35

Andrey писал(а):Если часов в 6 вечера ответа не будет напомните.
Ну что там с сортировкой?

Аватара пользователя
Andrey
Администратор
Администратор
Сообщения: 2345
Зарегистрирован: 02 фев 2012, 11:42
Откуда: Воронеж
Контактная информация:

Re: Внешняя многофазныя сортировка

Сообщение Andrey » 14 апр 2012, 19:36

Забыл. Скоро будет.

Аватара пользователя
Andrey
Администратор
Администратор
Сообщения: 2345
Зарегистрирован: 02 фев 2012, 11:42
Откуда: Воронеж
Контактная информация:

Re: Внешняя многофазныя сортировка

Сообщение Andrey » 14 апр 2012, 19:42

Нужна только вторая часть? Спрашиваю чтобы время впустую не тратить.

Аватара пользователя
Dmitriy
Сообщения: 12
Зарегистрирован: 02 фев 2012, 11:42

Re: Внешняя многофазныя сортировка

Сообщение Dmitriy » 14 апр 2012, 19:52

Andrey писал(а):Забыл. Скоро будет.
Спасибо!

Аватара пользователя
Andrey
Администратор
Администратор
Сообщения: 2345
Зарегистрирован: 02 фев 2012, 11:42
Откуда: Воронеж
Контактная информация:

Re: Внешняя многофазныя сортировка

Сообщение Andrey » 14 апр 2012, 20:33

Пока описываю на простом примере, потом если надо дам код.
Пусть дан массив: 7 8 6 3 2 9 1 0 23 12 56 24 78 30 20 11
На первом этапе считываем по S значений, сортируем и поочерёдно записываем их в два файла. Например S=2.
A: 7 8 2 9 12 23 30 78
B: 3 6 0 1 24 56 11 20
[hr][/hr]
На втором этапе начинается поочерёдное объединение. Будем брать по S значений из каждого файла и поочерёдно записывать в 2 других файла.
S=2
Содержимое файлов A и B после предыдущего шага
A: 7 8 2 9 12 23 30 78
B: 3 6 0 1 24 56 11 20
В результате преобразования в файлы C и D запишутся данные следующим образом
C: 3 6 7 8 12 23 24 56
D: 0 1 2 9 11 30 20 78
[hr][/hr]
Увеличиваем S в 2 раза. И точно также объединяем данные из файлов C и D, беря из них по 4 символа и записывая в A и B.
S=4
Содержимое файлов C и D после предыдущего шага
C: 3 6 7 8 12 23 24 56
D: 0 1 2 9 11 30 20 78
В результате преобразования в файлы A и B запишутся данные следующим образом
A: 0 1 2 3 6 7 8 9
B: 11 12 20 23 24 30 56 78
[hr][/hr]
S=8
Содержимое файлов A и B после предыдущего шага
A: 0 1 2 3 6 7 8 9
B: 11 12 20 23 24 30 56 78
В результате преобразования в файлы C и D запишутся данные следующим образом
C: 0 1 2 3 6 7 8 9 11 12 20 23 24 30 56 78
D:
Вот так постепенно в файле C получили полностью отсортированный массив.

Если непонятно могу попробовать рассказать подробнее.

Аватара пользователя
Dmitriy
Сообщения: 12
Зарегистрирован: 02 фев 2012, 11:42

Re: Внешняя многофазныя сортировка

Сообщение Dmitriy » 19 апр 2012, 19:40

Andrey, Огромное спасибо! Но можно код еще посмотреть) ???

Аватара пользователя
Andrey
Администратор
Администратор
Сообщения: 2345
Зарегистрирован: 02 фев 2012, 11:42
Откуда: Воронеж
Контактная информация:

Re: Внешняя многофазныя сортировка

Сообщение Andrey » 19 апр 2012, 19:57

Теперь завтра вечером, т.к. я не дома, а приеду поздно.

Аватара пользователя
Dmitriy
Сообщения: 12
Зарегистрирован: 02 фев 2012, 11:42

Re: Внешняя многофазныя сортировка

Сообщение Dmitriy » 26 апр 2012, 20:10

Andrey писал(а):Теперь завтра вечером, т.к. я не дома, а приеду поздно.
ну так что)

Аватара пользователя
Andrey
Администратор
Администратор
Сообщения: 2345
Зарегистрирован: 02 фев 2012, 11:42
Откуда: Воронеж
Контактная информация:

Re: Внешняя многофазныя сортировка

Сообщение Andrey » 26 апр 2012, 20:20

Блин, что-то из-за важных дел про всё остальное забывать стал. :(
На этот раз отметил что сделать надо.

Аватара пользователя
Dmitriy
Сообщения: 12
Зарегистрирован: 02 фев 2012, 11:42

Re: Внешняя многофазныя сортировка

Сообщение Dmitriy » 26 апр 2012, 20:23

ждемс

Аватара пользователя
Dmitriy
Сообщения: 12
Зарегистрирован: 02 фев 2012, 11:42

Re: Внешняя многофазныя сортировка

Сообщение Dmitriy » 26 апр 2012, 21:06

ну как продвигается?

Аватара пользователя
Andrey
Администратор
Администратор
Сообщения: 2345
Зарегистрирован: 02 фев 2012, 11:42
Откуда: Воронеж
Контактная информация:

Re: Внешняя многофазныя сортировка

Сообщение Andrey » 26 апр 2012, 21:09

Ну так не сегодня теперь. Я имел ввиду что отметил в это в списке того что надо сделать, завтра всё будет. Сейчас не могу, т.к. завтра у меня день тяжёлый, к нему готовиться надо.

Ответить