-
[Introduction to Algorithms, CLRS] Exercises 2.3-2알고리즘 2017. 12. 30. 20:11
This is a solution for Introduction to Algorithms. I write this for my study purpose.
Exercises 2.3-2
Rewrite the MERGE procedure so that it does not use sentinels, instead stopping once either array L or R has had all its elements copied back to A and then copying the remainder of the other array back into A.
Answer:
MERGE(A, p, q, r)
1 n1 = q - p + 1
2 n2 = r - q
3 let L[1..n1 + 1] and R[1..n2 + 1] be new arrays
4 for i = 1 to n1
5 L[i] = A[p + i - 1]
6 for j = 1 to n2
7 R[j] = A[q + j]
8 i = 1
9 j = 1
10 k = 1
11 for k = p to r
12 if L[i] <= R[j]
13 A[k] = L[i]
14 i = i +1
15 else A[k] = R[j]
16 j = j + 1
17 if i <= n1
18 while k <= r
19 A[k] = L[i]
20 i = i + 1
21 else while k <= r
22 A[k] = R[j]
23 j = j + 1
'알고리즘' 카테고리의 다른 글
[Introduction to Algorithms, CLRS] Exercises 2.3-4 (0) 2018.02.10 [Introduction to Algorithms, CLRS] Exercises 2.3-3 (0) 2018.01.27 [Introduction to Algorithms, CLRS] Exercises 2.3-1 (0) 2017.12.30 [Introduction to Algorithms, CLRS] Exercises 2.2-4 (0) 2017.12.24 [Introduction to Algorithms, CLRS] Exercises 2.2-3 (0) 2017.12.23