ادغام k آرایه مرتب — راهنمای کاربردی

1// C++ program to merge K sorted arrays 
2  
3#include <iostream> 
4#define n 4 
5  
6using namespace std; 
7  
8// Function to perform merge operation 
9void merge(int l, int r, int* output) 
10{ 
11    // to store the starting point of left 
12    // and right array 
13    int l_in = l * n, r_in = ((l + r) / 2 + 1) * n; 
14  
15    // to store the size of left and 
16    // right array 
17    int l_c = ((l + r) / 2 - l + 1) * n; 
18    int r_c = (r - (l + r) / 2) * n; 
19  
20    // array to temporarily store left 
21    // and right array 
22    int l_arr[l_c], r_arr[r_c]; 
23  
24    // storing data in left array 
25    for (int i = 0; i < l_c; i++) 
26        l_arr[i] = output[l_in + i]; 
27  
28    // storing data in right array 
29    for (int i = 0; i < r_c; i++) 
30        r_arr[i] = output[r_in + i]; 
31  
32    // to store the current index of 
33    // temporary left and right array 
34    int l_curr = 0, r_curr = 0; 
35  
36    // to store the current index 
37    // for output array 
38    int in = l_in; 
39  
40    // two pointer merge for two sorted arrays 
41    while (l_curr + r_curr < l_c + r_c) { 
42        if (r_curr == r_c || (l_curr != l_c &&  
43            l_arr[l_curr] < r_arr[r_curr])) 
44            output[in] = l_arr[l_curr], l_curr++, in++; 
45        else
46            output[in] = r_arr[r_curr], r_curr++, in++; 
47    } 
48} 
49  
50// Code to drive merge-sort and 
51// create recursion tree 
52void divide(int l, int r, int* output, 
53            int arr[][n]) 
54{ 
55    if (l == r) { 
56  
57        /* base step to initialize the output 
58           array before performing merge  
59           operation */
60        for (int i = 0; i < n; i++) 
61            output[l * n + i] = arr[l][i]; 
62  
63        return; 
64    } 
65  
66    // to sort left half 
67    divide(l, (l + r) / 2, output, arr); 
68  
69    // to sort right half 
70    divide((l + r) / 2 + 1, r, output, arr); 
71  
72    // merge the left and right half 
73    merge(l, r, output); 
74} 
75  
76// Driver Cunction 
77int main() 
78{ 
79    // input 2D-array 
80    int arr[][n] = { { 5, 7, 15, 18 }, 
81                     { 1, 8, 9, 17 }, 
82                     { 1, 4, 7, 7 } }; 
83  
84    // Number of arrays 
85    int k = sizeof(arr) / sizeof(arr[0]); 
86  
87    // Output array 
88    int* output = new int[n * k]; 
89  
90    divide(0, k - 1, output, arr); 
91  
92    // Print merged array 
93    for (int i = 0; i < n * k; i++) 
94        cout << output[i] << " "; 
95  
96    return 0; 
97}

1// Java program to merge K sorted arrays  
2import java.util.*; 
3  
4class GFG 
5{ 
6  
7static int n = 4;  
8  
9// Function to perform merge operation  
10static void merge(int l, int r, int[] output)  
11{  
12    // to store the starting point of left  
13    // and right array  
14    int l_in = l * n, r_in = ((l + r) / 2 + 1) * n;  
15  
16    // to store the size of left and  
17    // right array  
18    int l_c = ((l + r) / 2 - l + 1) * n;  
19    int r_c = (r - (l + r) / 2) * n;  
20  
21    // array to temporarily store left  
22    // and right array  
23    int l_arr[] = new int[l_c], r_arr[] = new int[r_c];  
24  
25    // storing data in left array  
26    for (int i = 0; i < l_c; i++)  
27        l_arr[i] = output[l_in + i];  
28  
29    // storing data in right array  
30    for (int i = 0; i < r_c; i++)  
31        r_arr[i] = output[r_in + i];  
32  
33    // to store the current index of  
34    // temporary left and right array  
35    int l_curr = 0, r_curr = 0;  
36  
37    // to store the current index  
38    // for output array  
39    int in = l_in;  
40  
41    // two pointer merge for two sorted arrays  
42    while (l_curr + r_curr < l_c + r_c) 
43    {  
44        if (r_curr == r_c || (l_curr != l_c &&  
45            l_arr[l_curr] < r_arr[r_curr]))  
46        { 
47            output[in] = l_arr[l_curr]; l_curr++; in++;  
48        } 
49        else
50        { 
51            output[in] = r_arr[r_curr]; r_curr++; in++;  
52        } 
53    }  
54}  
55  
56// Code to drive merge-sort and  
57// create recursion tree  
58static void divide(int l, int r, int[] output,  
59                                int arr[][])  
60{  
61    if (l == r) 
62    {  
63  
64        /* base step to initialize the output  
65        array before performing merge  
66        operation */
67        for (int i = 0; i < n; i++)  
68            output[l * n + i] = arr[l][i];  
69  
70        return;  
71    }  
72  
73    // to sort left half  
74    divide(l, (l + r) / 2, output, arr);  
75  
76    // to sort right half  
77    divide((l + r) / 2 + 1, r, output, arr);  
78  
79    // merge the left and right half  
80    merge(l, r, output);  
81}  
82  
83// Driver Code 
84public static void main(String[] args)  
85{ 
86    // input 2D-array  
87    int arr[][] = { { 5, 7, 15, 18 },  
88                    { 1, 8, 9, 17 },  
89                    { 1, 4, 7, 7 } };  
90  
91    // Number of arrays  
92    int k = arr.length;  
93  
94    // Output array  
95    int[]output = new int[n * k];  
96  
97    divide(0, k - 1, output, arr);  
98  
99    // Print merged array  
100    for (int i = 0; i < n * k; i++)  
101            System.out.print(output[i] + " "); 
102} 
103} 
104  
105/* This code contributed by PrinciRaj1992 */

1# Python3 program to merge K sorted arrays  
2n = 4 ; 
3  
4# Function to perform merge operation  
5def merge(l, r, output) : 
6      
7    # to store the starting point of  
8    # left and right array  
9    l_in = l * n ; 
10    r_in = ((l + r) // 2 + 1) * n;  
11  
12    # to store the size of left and  
13    # right array  
14    l_c = ((l + r) // 2 - l + 1) * n;  
15    r_c = (r - (l + r) // 2) * n;  
16  
17    # array to temporarily store left  
18    # and right array  
19    l_arr = [0] * l_c; r_arr = [0] * r_c;  
20  
21    # storing data in left array  
22    for i in range(l_c) : 
23        l_arr[i] = output[l_in + i];  
24  
25    # storing data in right array  
26    for i in range(r_c) : 
27        r_arr[i] = output[r_in + i];  
28  
29    # to store the current index of  
30    # temporary left and right array  
31    l_curr = 0 ; r_curr = 0;  
32  
33    # to store the current index  
34    # for output array  
35    in1 = l_in;  
36  
37    # two pointer merge for two sorted arrays  
38    while (l_curr + r_curr < l_c + r_c) : 
39        if (r_curr == r_c or (l_curr != l_c and
40            l_arr[l_curr] < r_arr[r_curr])) : 
41            output[in1] = l_arr[l_curr];  
42            l_curr += 1; in1 += 1;  
43        else : 
44            output[in1] = r_arr[r_curr]; 
45            r_curr += 1; in1 += 1;  
46  
47# Code to drive merge-sort and  
48# create recursion tree  
49def divide(l, r, output, arr) : 
50      
51    if (l == r) :  
52  
53        # base step to initialize the output  
54        # array before performing merge  
55        # operation  
56        for i in range(n) : 
57            output[l * n + i] = arr[l][i];  
58  
59        return;  
60      
61    # to sort left half  
62    divide(l, (l + r) // 2, output, arr);  
63  
64    # to sort right half  
65    divide((l + r) // 2 + 1, r, output, arr);  
66  
67    # merge the left and right half  
68    merge(l, r, output);  
69  
70# Driver code  
71if __name__ == "__main__" : 
72  
73    # input 2D-array  
74    arr = [[ 5, 7, 15, 18 ],  
75           [ 1, 8, 9, 17 ],  
76           [ 1, 4, 7, 7 ]];  
77      
78    # Number of arrays  
79    k = len(arr);  
80      
81    # Output array 
82    output = [0] * (n * k);  
83      
84    divide(0, k - 1, output, arr);  
85      
86    # Print merged array  
87    for i in range(n * k) : 
88        print(output[i], end = " ");  
89  
90# This code is contributed by Ryuga

1// C# program to merge K sorted arrays  
2using System; 
3  
4class GFG 
5{ 
6  
7static int n = 4;  
8  
9// Function to perform merge operation  
10static void merge(int l, int r, int[] output)  
11{  
12    // to store the starting point of left  
13    // and right array  
14    int l_in = l * n, r_in = ((l + r) / 2 + 1) * n;  
15  
16    // to store the size of left and  
17    // right array  
18    int l_c = ((l + r) / 2 - l + 1) * n;  
19    int r_c = (r - (l + r) / 2) * n;  
20  
21    // array to temporarily store left  
22    // and right array  
23    int []l_arr = new int[l_c]; 
24    int []r_arr = new int[r_c];  
25  
26    // storing data in left array  
27    for (int i = 0; i < l_c; i++)  
28        l_arr[i] = output[l_in + i];  
29  
30    // storing data in right array  
31    for (int i = 0; i < r_c; i++)  
32        r_arr[i] = output[r_in + i];  
33  
34    // to store the current index of  
35    // temporary left and right array  
36    int l_curr = 0, r_curr = 0;  
37  
38    // to store the current index  
39    // for output array  
40    int index = l_in;  
41  
42    // two pointer merge for two sorted arrays  
43    while (l_curr + r_curr < l_c + r_c) 
44    {  
45        if (r_curr == r_c || (l_curr != l_c &&  
46            l_arr[l_curr] < r_arr[r_curr]))  
47        { 
48            output[index] = l_arr[l_curr]; l_curr++; index++;  
49        } 
50        else
51        { 
52            output[index] = r_arr[r_curr]; r_curr++; index++;  
53        } 
54    }  
55}  
56  
57// Code to drive merge-sort and  
58// create recursion tree  
59static void divide(int l, int r, int[] output,  
60                                int [,]arr)  
61{  
62    if (l == r) 
63    {  
64  
65        /* base step to initialize the output  
66        array before performing merge  
67        operation */
68        for (int i = 0; i < n; i++)  
69            output[l * n + i] = arr[l, i];  
70  
71        return;  
72    }  
73  
74    // to sort left half  
75    divide(l, (l + r) / 2, output, arr);  
76  
77    // to sort right half  
78    divide((l + r) / 2 + 1, r, output, arr);  
79  
80    // merge the left and right half  
81    merge(l, r, output);  
82}  
83  
84// Driver Code 
85public static void Main(String[] args)  
86{ 
87    // input 2D-array  
88    int [,]arr = { { 5, 7, 15, 18 },  
89                    { 1, 8, 9, 17 },  
90                    { 1, 4, 7, 7 } };  
91  
92    // Number of arrays  
93    int k = arr.GetLength(0);  
94  
95    // Output array  
96    int []output = new int[n * k];  
97  
98    divide(0, k - 1, output, arr);  
99  
100    // Print merged array  
101    for (int i = 0; i < n * k; i++)  
102            Console.Write(output[i] + " "); 
103} 
104} 
105  
106// This code has been contributed by 29AjayKumar