Алгоритмы и структуры данных на С++. Аксёнова Е.А - 71 стр.

UptoLike

ВУЗ: 

ПетрГУ | Петрозаводск

Составители: 

Рубрика: 

5.5. Сортировка слиянием фон Неймана 71
c=a[i];
a[i]=a[j];
a[j]=c;
}
c=a[i];
a[i]=a[r];
a[r]=c;
return i;
}
5.5. Сортировка слиянием фон Неймана
Этот метод основан на последовательном слиянии упорядоченных
массивов в большие упорядоченные массивы.
Пусть надо упорядочить массив (7, 1, 3, 2, 5, 6, 8, 4). Сливая одиноч-
ные элементы в пары и записывая пары в новый массив, получим
массив упорядоченных пар: (1, 7), (2, 3), (5, 6), (4, 8). Теперь сливаем
упорядоченные пары в упорядоченные четверки и, записывая их на
место первоначального массива, получаем (1, 2, 3, 7) и (4, 5, 6, 8). И,
наконец, сливаем четверки в упорядоченную восьмерку чисел и полу-
чаем (1, 2, 3, 4, 5, 6, 7, 8).
Алгоритм фон Неймана имеет среднее время работы T = C·n·log
2
n
и требует двойную память.
В процессе работы алгоритму приходится решать следующую за-
дачу: имея два упорядоченных массива x
1
≤ x
2
≤ ... ≤ x
m
и y
1
≤ y
2
≤
... ≤ y
n
, надо сделать из них один упорядоченный массив z
1
≤ z
2
≤
... ≤ z
m+n
. Пусть i, j, k – счетчики массивов x, y, z соответственно.
Алгоритм двухпутевого слияния в пошаговой форме:
D1: i = 1; j = 1; k = 1;
D2: если x
i
≤ y
j
, то перейти к шагу D5;
D3: z
k
= y
j
; k = k + 1; j = j + 1;
если j ≤ n, то перейти к шагу D2;
D4: z
k
...z
m+n
= x
i
...x
m
;
D5: z
k
= x
i
; k = k + 1; i = i + 1;
если i ≤ m, то перейти к шагу D2;
D6: z
k
...z
m+n
= y
j
...y
n
.
5.5.    Сортировка слиянием фон Неймана                                 71


             c=a[i];
             a[i]=a[j];
             a[j]=c;
        }

        c=a[i];
        a[i]=a[r];
        a[r]=c;
        return i;
}

            5.5. Сортировка слиянием фон Неймана

     Этот метод основан на последовательном слиянии упорядоченных
массивов в большие упорядоченные массивы.
     Пусть надо упорядочить массив (7, 1, 3, 2, 5, 6, 8, 4). Сливая одиноч-
ные элементы в пары и записывая пары в новый массив, получим
массив упорядоченных пар: (1, 7), (2, 3), (5, 6), (4, 8). Теперь сливаем
упорядоченные пары в упорядоченные четверки и, записывая их на
место первоначального массива, получаем (1, 2, 3, 7) и (4, 5, 6, 8). И,
наконец, сливаем четверки в упорядоченную восьмерку чисел и полу-
чаем (1, 2, 3, 4, 5, 6, 7, 8).
     Алгоритм фон Неймана имеет среднее время работы T = C·n·log2 n
и требует двойную память.
     В процессе работы алгоритму приходится решать следующую за-
дачу: имея два упорядоченных массива x1 ≤ x2 ≤ ... ≤ xm и y1 ≤ y2 ≤
... ≤ yn , надо сделать из них один упорядоченный массив z1 ≤ z2 ≤
... ≤ zm+n . Пусть i, j, k – счетчики массивов x, y, z соответственно.

    Алгоритм двухпутевого слияния в пошаговой форме:

       D1: i = 1; j = 1; k = 1;
       D2: если xi ≤ yj , то перейти к шагу D5;
       D3: zk = yj ; k = k + 1; j = j + 1;
           если j ≤ n, то перейти к шагу D2;
       D4: zk ...zm+n = xi ...xm ;
       D5: zk = xi ; k = k + 1; i = i + 1;
           если i ≤ m, то перейти к шагу D2;
       D6: zk ...zm+n = yj ...yn .

Страницы