SCALANIE UPORZADKOWANYCH PODCIĄGÓW
ALGORYTM
Krok 1 Dopóki jeden ze zbiorów A, B nie jest pusty wykonuj Krok 2
Krok 2 Mniejszy z elementów początkowych zbiorów A, B przenieś do C
Kork 3 Dopisz do C pozostałe elementy z niepustego zbioru
STRUKTURA
Tablica A Tblica B
1 2 3 4 ... d1 1 2 3 ...d2
0 |
1 |
2 |
4 |
6 |
1 |
4 |
7 |
9 |
↑ ↑
w_1 w_2
Tablica C
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
↑
w_1 d3
Tablica C po wykonaniu algorytmu
0 |
1 |
1 |
2 |
4 |
4 |
6 |
7 |
9 |
↑
w_1 d3
Kiedy zbiór jest pusty? Gdy w > d albo nie jest pusty gdy w <= d
Algorytm + Struktura = Program
PSEUDO KOD
w_1, w_2, w_3 = 1
Dopóki (w_1 <= d1 i w_2<= d2) // Krok 1
- Jeśli A[w_1] < B[w_1] to // Krok 2
C[w_3] = A[w_1]
w_1++
else C[w_3] = B[w_1]
w_2++
- w_3++
Jeśli w_1 > d1 to // Krok 3
For( i = w_2 do d2)
- C[w_3] = B[i]
- w_3++
else
For( i = w_1 do d1)
- C[w_3] = A[i]
- w_3++