ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Многофазная сортировка
13 сообщений из 13, страница 1 из 1
Многофазная сортировка
    #36383062
proxy1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
proxy1
Участник
В книге Макконнела приведен алгоритм: Внешняя многофазная сортировка слиянием

Его первая фаза:
автор
На первом шаге мы прочитаем S записей и отсортируем их с помощью подходящей внутренней сортировки. Этот набор уже отсортированных записей перепишем в файл А. Затем прочитаем еще S записей, отсортируем их и перепишем в файл В. Этот процесс продолжается, причем отсортированные блоки записей пишутся попеременно то в файл А, то в файл В. Вот алгоритм, реализующий первый этап:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
CreateRuns(S)
S размер создаваемых отрезков
CurrentFile=A
while конец входного файла не достигнут do
    read S записей из входного файла
    sort S записей
    if CurrentFile=A then
        CurrentFile=B
    else
        CurrrentFile=A
    end if
end while

автор
После того, как входной файл полностью разбит на отсортированные отрезки, мы готовы перейти ко второму шагу - - слиянию этих отрезков. Каждый из файлов А и В содержит некоторую последова-
тельность отсортированных отрезков, однако, как и в случае сортировки слиянием, мы ничего не можем сказать о порядке записей в двух различных отрезках.
Процесс слияния будет аналогичен функции MergeLists из § 3.6, однако теперь вместо того, чтобы переписывать записи в новый массив, мы будем записывать их в новый файл. Поэтому мы начинаем с чтения половинок первых отрезков из файлов А и В. Читаем мы лишь по половине отрезков, поскольку мы уже выяснили, что в памяти может находиться одновременно лишь S записей, а нам нужны записи из обоих файлов. Будем теперь сливать эти половинки отрезков в один отрезок файла С. После того, как одна из половинок закончится, мы прочтем вторую половинку из того же файла. Когда обработка одного из отрезков будет завершена, конец второго отрезка будет переписан
в файл С. После того, как слияние первых двух отрезков из файлов А и В будет завершено, следующие два отрезка сливаются в файл D. Этот процесс слияния отрезков продолжается с попеременной записью слитых отрезков в файлы С и D. По завершении мы получаем два файла,
разбитых на отсортированные отрезки длины 2S. Затем процесс повторяется, причем отрезки читаются из файлов С и D, а слитые отрезки длины 4S записываются в файлы А и В. Ясно, что в конце концов отрезки сольются в один отсортированный список в одном из файлов.
Вот алгоритм осуществления второго этапа:


Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
PolyPhaseMerge(S)
S размер исходных отрезков
Size=S
Input1=A
Input2=B
Current Output=C
while not done do
    while отрезки не кончились do
        слить отрезок длины Size из файла Input1
            с отрезком длины Size из файла Input2
            записав результат в CurrentOutput
        if (CurrentOutput=A) then
            CurrentOutput=B
        elsif (CurrentOutput=B) then
            CurrrentOutput=A
        elsif (CurrentOutput=C) then
            Currrent Output=D
        elsif (CurrentOutput=D) then
            CurrrentOutput=C
        end if
    end while
    Size=Size* 2 
    if (Input1=A) then
        Input1=C
        Input2=D
        Current Output=A
    else
        Input1=A
        Input2=B
        CurrentOutput=C
    end if
end while
...
Рейтинг: 0 / 0
23.12.2009, 18:48:10
| Ответить | Цитировать | Написать  
Многофазная сортировка
    #36383097
proxy1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
proxy1
Участник
возьмем файл со следующим содержимым:

4 2 9 0 5 1 6 3 8 7

1-й этап:

A: 2 4 1 5 7 8
B: 0 9 3 6
C:
D:

затем:
A: 2 4 1 5 7 8
B: 0 9 3 6
C: 0 2 4 9 7 8
D: 1 3 5 6

A: 0 1 2 3 4 5 6 9
B: 7 8
C: 0 2 4 9 7 8
D: 1 3 5 6

A: 0 1 2 3 4 5 6 9
B: 7 8
C: 0 7 1 8 2 3 4 5 6 9
D:

В итоге в файле С получаем якобы отсортированную последовательность, что явно не так.
Где я ошибся и алгоритм не так понял?
...
Рейтинг: 0 / 0
23.12.2009, 18:58:40
| Ответить | Цитировать | Написать  
Многофазная сортировка
    #36384730
Фотография krvsa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
krvsa
Участник
proxy1Где я ошибся и алгоритм не так понял?
В алгоритме написаноавторпрочитаем S записей
Чему у тебя равно S?
...
Рейтинг: 0 / 0
24.12.2009, 15:15:15
| Ответить | Цитировать | Написать  
Многофазная сортировка
    #36385606
proxy1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
proxy1
Участник
krvsa,

Пробовал S=2 и S=4.
Просто какой-то момент алгоритма не освещен, видимо.
...
Рейтинг: 0 / 0
24.12.2009, 23:25:49
| Ответить | Цитировать | Написать  
Многофазная сортировка
    #36385976
Фотография krvsa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
krvsa
Участник
Я для интереса накропал програмульку и все получается...

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
>d ^tmp
 
A:  2   4   1   5   7   8 
B:  0   9   3   6 
C:  0   2   4   9   7   8 
D:  1   3   5   6 
A:  0   1   2   3   4   5   6   9 
B:  7   8 
C:  0   1   2   3   4   5   6   7   8   9 
D:
 
Все!
C:  0   1   2   3   4   5   6   7   8   9 
D:

Вот пример програмульки.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
TEST
 n
 s s= 2 
 s str="4,2,9,0,5,1,6,3,8,7"
 for i= 1 : 1 :$l(str,",") s arr(i)=$p(str,",",i)
 // Первый этап
 s cur="A"
 s i= 1 
 while $d(arr(i)) {
	 k tmp
	 for j= 0 : 1 :s- 1  {
		 q:$d(arr(i+j))= 0 
		 s tmp(arr(i+j))=""
	 }
	 s i=i+s
	 s j=""
	 do {
		 s j=$o(tmp(j))
		 q:j=""
		 s k=$o(@cur@(""),- 1 )+ 1 
		 s @cur@(k)=j
	 } while  1 
	 if cur="A" {
		 s cur="B"
	 } else {
		 s cur="A"
	 }
 }
 d W("A")
 d W("B")
 // Последующие этапы
 s in1="A"
 s in2="B"
 s ou1="C"
 s ou2="D"
 s cur="C"
 while $d(@in1),$d(@in2) {
	 s i= 1 
	 k @ou1
	 k @ou2
	 while $d(@in1@(i))!$d(@in2@(i)) {
		 k tmp
		 d SAVE( 0 ,s/ 2 ,in1)
		 d SAVE( 0 ,s/ 2 ,in2)
		 d SAVE(s/ 2 ,s,in1)
		 d SAVE(s/ 2 ,s,in2)
		 s i=i+s
		 s j=""
		 do {
			 s j=$o(tmp(j))
			 q:j=""
			 s k=$o(@cur@(""),- 1 )+ 1 
			 s @cur@(k)=j
		 } while  1 
		 s cur=$$Cur
	 }
	 d W(ou1)
	 d W(ou2)
	 s s=s* 2 
	 if in1="A" {
		 s in1="C"
		 s in2="D"
		 s ou1="A"
		 s ou2="B"
		 s cur="A"
	 } else {
		 s in1="A"
		 s in2="B"
		 s ou1="C"
		 s ou2="D"
		 s cur="C"
	 }
 }
 w !!,"Все!"
 d W(in1)
 d W(in2)
 q
SAVE(Beg,End,Arr) // Запись в буфер и сортировка
 n j
 for j=Beg: 1 :End- 1  {
	 q:$d(@Arr@(i+j))= 0 
	 s tmp(@Arr@(i+j))=""
 }
 q
Cur() // Текущие данные
 q:cur="C" "D"
 q:cur="D" "C"
 q:cur="A" "B"
 q:cur="B" "A"
 q ""
W(Arr) // Вывод данных
 n i
 w !,Arr,":"
 for i= 1 : 1 :$o(@Arr@(""),- 1 ) {
	 w " ",@Arr@(i)
 }
 q
----------
Cache for Windows (x86-32) 2007.1.3 (Build 607) Wed Oct 17 2007 02:12:09 EDT
...
Рейтинг: 0 / 0
25.12.2009, 10:24:15
| Ответить | Цитировать | Написать  
Многофазная сортировка
    #36386015
Фотография krvsa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
krvsa
Участник
Может вот так будет более наглядно...

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
>d ^tmp
 
A:  2   4   1   5   7   8 
B:  0   9   3   6 
s= 2 
Преобразовывается:
A:  2   4   1   5   7   8 
B:  0   9   3   6 
Получается:
C:  0   2   4   9   7   8 
D:  1   3   5   6 
s= 4 
Преобразовывается:
C:  0   2   4   9   7   8 
D:  1   3   5   6 
Получается:
A:  0   1   2   3   4   5   6   9 
B:  7   8 
s= 8 
Преобразовывается:
A:  0   1   2   3   4   5   6   9 
B:  7   8 
Получается:
C:  0   1   2   3   4   5   6   7   8   9 
D:
 
Все!
C:  0   1   2   3   4   5   6   7   8   9 
D:
----------
Cache for Windows (x86-32) 2007.1.3 (Build 607) Wed Oct 17 2007 02:12:09 EDT
...
Рейтинг: 0 / 0
25.12.2009, 10:43:58
| Ответить | Цитировать | Написать  
Многофазная сортировка
    #36386031
Фотография krvsa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
krvsa
Участник
proxy1A: 0 1 2 3 4 5 6 9
B: 7 8
C: 0 7 1 8 2 3 4 5 6 9
D:

Где я ошибся и алгоритм не так понял?
Тут s=8 и нужно брать по 4, а не по 1, как ты начал делать...
...
Рейтинг: 0 / 0
25.12.2009, 10:52:29
| Ответить | Цитировать | Написать  
Многофазная сортировка
    #36386188
proxy1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
proxy1
Участник
krvsa,

Дело в том, что сама по себе внешняя сортировка применяется по той причине, что в оперативной памяти мало места и поэтому нельзя сразу все данные поместить в нее и отсортировать обычным методом сортировки. В этом алгоритме считается, что доступен объем памяти, вмещающий S элементов:
Код: plaintext
Читаем мы лишь по половине отрезков, поскольку мы уже выяснили, что в памяти может находиться одновременно лишь S записей, а нам нужны записи из обоих файлов.
И мне непонятно, каким образом тогда оперировать цепочками 2S, 4S и т.д. Каким-то образом разделять их и обрабатывать по частям?
...
Рейтинг: 0 / 0
25.12.2009, 12:05:55
| Ответить | Цитировать | Написать  
Многофазная сортировка
    #36386589
Фотография krvsa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
krvsa
Участник
proxy1И мне непонятно, каким образом тогда оперировать цепочками 2S, 4S и т.д.
Но они-то множат...

Код: plaintext
1.
2.
3.
4.
...
слить отрезок длины Size из файла Input1 с отрезком длины Size из файла Input2
...
Size=Size* 2 
...
...
Рейтинг: 0 / 0
25.12.2009, 14:30:55
| Ответить | Цитировать | Написать  
Многофазная сортировка
    #36386603
Фотография krvsa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
krvsa
Участник
Сейчас проверил на s=2 и s=4 - не сортирует, если убрать увеличение "шага"... Там получается какое-то "мыло-мочало"... Т.е. повторяющиеся последовательности.
----------
Cache for Windows (x86-32) 2007.1.3 (Build 607) Wed Oct 17 2007 02:12:09 EDT
...
Рейтинг: 0 / 0
25.12.2009, 14:35:42
| Ответить | Цитировать | Написать  
Многофазная сортировка
    #36386641
Фотография krvsa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
krvsa
Участник
Вот такая фигня получается если просто s=4

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
s= 4 
Преобразовывается:
A:  0   1   2   3   7   8 
B:  4   5   6   9 
Получается:
C:  0   1   2   3   4   5   6   9 
D:  7   8 
s= 4 
Преобразовывается:
C:  0   1   2   3   4   5   6   9 
D:  7   8 
Получается:
A:  0   1   2   3   7   8 
B:  4   5   6   9

круг замкнулся...
----------
Cache for Windows (x86-32) 2007.1.3 (Build 607) Wed Oct 17 2007 02:12:09 EDT
...
Рейтинг: 0 / 0
25.12.2009, 14:45:29
| Ответить | Цитировать | Написать  
Многофазная сортировка
    #36395490
Emery
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Emery
Участник
Если интересно, то вот «Нелинейная» demo реализация сортировки естественным слиянием (Natural Merge Sort) на Visual FoxPro» с картинками. Сейчас пишу тот же самый алгоритм на С++. Кстати, этот алгоритм эффективнее алгоритма, рассматриваемого вами.
...
Рейтинг: 0 / 0
01.01.2010, 15:50:39
| Ответить | Цитировать | Написать  
Многофазная сортировка
    #36412267
Emery
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Emery
Участник
А вот "Реализация на С++ внешней сортировки «естественным слиянием» (Natural Merge Sort)"
...
Рейтинг: 0 / 0
15.01.2010, 14:04:26
| Ответить | Цитировать | Написать  
13 сообщений из 13, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Многофазная сортировка
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&gotonew=1&tid=1343953]:
 0ms
get settings:
 5ms
get forum list:
 14ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 286ms
get topic data:
 10ms
get first new msg:
 5ms
get forum data:
 2ms
get page messages:
 61ms
get tp. blocked users:
 2ms
others: 198ms
total:  589ms
созд. / загр.: 589ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]