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

۵۵۱ بازدید
آخرین به‌روزرسانی: ۲۰ تیر ۱۴۰۲
زمان مطالعه: ۸ دقیقه
ادغام k آرایه مرتب — راهنمای کاربردی

K آرایه مرتب شده داده شده است. هر آرایه دارای اندازه N است. هدف ادغام k آرایه مرتب شده در یک آرایه مرتب است. مثال زیر در این رابطه جالب توجه است.

Input : arr[][] = {{5, 7, 15, 18},
                   {1, 8, 9, 17},
                   {1, 4, 7, 7}}
Output :  {1, 1, 4, 5, 7, 7, 7, 8, 9, 15, 17, 18}

Input : arr[][] = {{3, 2, 1}
                   {6, 5, 4}}
Output :  {1, 2, 3, 4, 5, 6}

برای درک بهتر این مطلب، نیاز به آشنایی با «الگوریتم مرتب‌سازی ادغامی» (Merge Sort) است. یک راهکار ساده برای ادغام k آرایه مرتب شده، الحاق همه آرایه‌ها، یکی پس از دیگری و سپس، مرتب‌سازی آن‌ها است. پیچیدگی زمانی این عملیات از درجه O(N*k * log(N*k))‎ است. در روش موثرتر، به K آرایه، به عنوان یک حالت متوسط از الگوریتم مرتب‌سازی ادغامی نگاه می‌شود.

از آنجا که K آرایه مرتب شده در حال حاضر وجود دارد، تنها نیاز به ادغام کردن K آرایه است. با ادغام آن‌ها، یک درخت بازگشتی با ارتفاع log(k)‎ ساخته می‌شود که در هر گام از آن، تعداد آرایه‌های باقیمانده نصف می‌شود. در هر ارتفاعی، الگوریتم به مدت O(N*k)‎ به طول خواهد انجامید. بنابراین، پیچیدگی زمانی کاهش پیدا می‌کند و برابر با O( N*k * log(k) )‎ خواهد بود.

الگوریتم ادغام k آرایه مرتب شده

  1. آرایه خروجی با اندازه  N*k را مقداردهی اولیه کن.
  2. تابع divide را فراخوانی کن. با l و r، طیف آرایه‌هایی که ادغام می‌شوند را نمایش بده و بنابراین بین 0 تا k-1 متغیر باش.
  3. در هر گام، نیمه سمت چپ و راست دامنه به صورت بازگشتی فراخوانی می‌شود، بنابراین این‌ها مرتب‌سازی می‌شوند و در آرایه خروجی نیز مرتب می‌شوند.
  4. پس از آن، نیمه سمت راست و چپ ادغام می‌شوند. برای ادغام کردن، نیاز به تعیین دامنه اندیس‌ها برای نیمه‌های سمت راست و چپ در آرایه خروجی است. می‌توان به سادگی این مورد را پیدا کرد.
    • بگذار بخش سمت چپ از اندیس  l * n از آرایه خروجی آغاز شود.
    • به طور مشابه، بخش سمت راست از اندیس l + r) / 2 + 1) * n‎)) آرایه خروجی آغاز می‌شود.

همچنین، باید طول بخش‌های سمت راست و چپ تعیین شود. همچنین، باید طول بخش‌های سمت راست و چپ تعیین شود. پس از آن، دو آرایه موقتی «l_arr» و «r_arr» برای ذخیره‌سازی مقادیر از بخش‌های راست و چپ مورد استفاده قرار می‌گیرند. در نهایت، از روش دو اشاره‌گر برای ادغام نتایج در بخش‌های سمت راست و چپ در هنگام اجرای ادغام استفاده می‌شود. در ادامه، پیاده‌سازی الگوریتم بالا ارائه شده است.

برنامه ادغام k آرایه مرتب شده در ++C

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}

برنامه ادغام k آرایه مرتب شده در جاوا

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 */

برنامه ادغام k آرایه مرتب شده در پایتون ۳

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

برنامه ادغام k آرایه مرتب شده در #C

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

خروجی قطعه کد بالا به صورت زیر است.

1 1 4 5 7 7 7 8 9 15 17 18

این مساله را می‌توان با استفاده از «هرم کمینه» (Min-Heap) نیز حل کرد.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۳ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeks
۲ دیدگاه برای «ادغام k آرایه مرتب — راهنمای کاربردی»

با سلام بهترین ساختار برای ادغام k لیست مرتب min heap است یا درخت جستجو و یا لیست دو طرفه خطی؟

سلام جوابش چی بود؟

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *