Блог

я не понимаю этот конкретный пример кода из geeksforgeeks по сортировке слиянием k-way. Более конкретно, я не понимаю, что такое «n» в цикле for в базовом случае для divide() . Это количество учащихся в каждом массиве? (который в данном случае равен 4)

Также не могли бы вы объяснить, что делает цикл for в divide() по отношению к процессу divide()? что должен означать базовый вариант (l == r)?

Спасибо.

Подход: Идея становится понятной, как только мы начинаем рассматривать k массивов как промежуточное состояние алгоритма сортировки слиянием. Поскольку существует k массивов, которые уже отсортированы, объедините k массивов. Создайте рекурсивную функцию, которая будет принимать k массивов, делить их на две части и вызывать функцию рекурсивно с каждой половиной. Базовыми случаями являются случаи, когда значение k меньше 3. Смотрите эту статью о слиянии двух массивов за O (n) время.

Алгоритм: Инициализируйте выходной массив размером N *k. Вызовите функцию divide. Пусть l и r представляют диапазон массивов, которые должны быть объединены, и, следовательно, варьируются от 0 до k-1. На каждом шаге мы рекурсивно вызываем левую и правую половины диапазона, чтобы они были отсортированы и сохранены в выходном массиве. После этого мы объединяем левую и правую половины. Для слияния нам нужно определить диапазон индексов для левой и правой половин в выходном массиве. Мы можем легко найти это. Левая часть будет начинаться с индекса l * n выходного массива. Аналогично, правая часть будет начинаться с индекса ((l r) / 2 1) * n выходного массива.

 
import java.util.*; 
  
class GFG { 
  
    static int n = 4; 
  
    // Function to perform 
    // merge operation 
    static void merge( 
        int l, int r, int[] output) 
    { 
        // To store the starting point 
        // of left and right array 
        int l_in = l * n, r_in 
                          = ((l   r) / 2   1) * n; 
  
        // to store the size of left and 
        // right array 
        int l_c = ((l   r) / 2 - l   1) * n; 
        int r_c = (r - (l   r) / 2) * n; 
  
        // array to temporarily store left 
        // and right array 
        int l_arr[] = new int[l_c], 
            r_arr[] = new int[r_c]; 
  
        // storing data in left array 
        for (int i = 0; i < l_c; i  ) 
            l_arr[i] = output[l_in   i]; 
  
        // storing data in right array 
        for (int i = 0; i < r_c; i  ) 
            r_arr[i] = output[r_in   i]; 
  
        // to store the current index of 
        // temporary left and right array 
        int l_curr = 0, r_curr = 0; 
  
        // to store the current index 
        // for output array 
        int in = l_in; 
  
        // two pointer merge for two sorted arrays 
        while (l_curr   r_curr < l_c   r_c) { 
            if ( 
                r_curr == r_c 
                || (l_curr != l_c 
                    amp;amp; l_arr[l_curr] < r_arr[r_curr])) { 
                output[in] = l_arr[l_curr]; 
                l_curr  ; 
                in  ; 
            } 
            else { 
                output[in] = r_arr[r_curr]; 
                r_curr  ; 
                in  ; 
            } 
        } 
    } 
  
    // Code to drive merge-sort and 
    // create recursion tree 
    static void divide(int l, int r, int[] output, 
                       int arr[][]) 
    { 
        if (l == r) { 
  
            /* base step to initialize the output  
        array before performing merge  
        operation */
            for (int i = 0; i < n; i  ) 
                output[l * n   i] = arr[l][i]; 
  
            return; 
        } 
  
        // to sort left half 
        divide(l, (l   r) / 2, output, arr); 
  
        // to sort right half 
        divide((l   r) / 2   1, r, output, arr); 
  
        // merge the left and right half 
        merge(l, r, output); 
    } 
  
    // Driver Code 
    public static void main(String[] args) 
    { 
        // input 2D-array 
        int arr[][] = { { 5, 7, 15, 18 }, 
                        { 1, 8, 9, 17 }, 
                        { 1, 4, 7, 7 } }; 
  
        // Number of arrays 
        int k = arr.length; 
  
        // Output array 
        int[] output = new int[n * k]; 
  
        divide(0, k - 1, output, arr); 
  
        // Print merged array 
        for (int i = 0; i < n * k; i  ) 
            System.out.print(output[i]   " "); 
    } 
} 
  

откуда: https://www.geeksforgeeks.org/merge-k-sorted-arrays-set-3-using-divide-and-conquer-approach/?ref=rp

Я думаю, что это расширенная версия merge sort . Вот сценарий, мы k отсортировали массивы с n элементами (как вы их назвали students) в каждом. Цель состоит в том, чтобы иметь единый отсортированный массив ( output ) всех элементов, размер k*n которого равен . Поскольку k массивы отсортированы, нам просто нужен алгоритм для их объединения. Для этого в рекурсивной функции divide(l, r, output, arr) мы разделяем l-th r-th массивы на два набора и рекурсивно вызываем divide для них. Например, для k=3 нас есть l=0 и r=2 . В функции разделения, поскольку l!=r мы пропускаем первое if и вызываем две функции divide(0, 1, output, arr) and divide(2, 2, output, arr) . Опять же, при первом вызове функции мы вызываем divide(0, 0, output, arr) и divide(1, 1, output, arr) . Теперь, когда у нас есть l==r , мы должны сохранить l-й (равный r-му) массив для вывода (обратите внимание, что merge функция является функцией на месте). Для этого не забудьте преобразовать 2d массив A[n][m] в 1d массив B[n*m] , к которому мы можем получить доступ A[i][j] B[i*n j] . Для получения дополнительных разъяснений я поместил несколько отпечатков в функцию разделения:

 static void divide(int l, int r, int[] output, 
    int arr[][]) 
    { 
        if (l == r) { 
  
            /* base step to initialize the output  
                array before performing merge  
                operation */
            for (int i = 0; i < n; i  ) 
                output[l * n   i] = arr[l][i]; 

            System.out.println("After writing to output:");
            for (int i = 0; i < n * k; i  ) 
                System.out.print(output[i]   " ");
            System.out.println()
            return; 
        } 
  
        // to sort left half 
        divide(l, (l   r) / 2, output, arr); 
  
        // to sort right half 
        divide((l   r) / 2   1, r, output, arr); 
  
        // merge the left and right half 
        merge(l, r, output);
        System.out.print("After Merge:");
        for (int i = 0; i < n * k; i  ) 
                System.out.print(output[i]   " ");
        System.out.println();
    } 
  

и вот результат:

 After writing to output:
[5, 7, 15, 18, 0, 0, 0, 0, 0, 0, 0, 0]  # after divide(0, 0, output, arr)
After writing to output:
[5, 7, 15, 18, 1, 8, 9, 17, 0, 0, 0, 0] # after divide(1, 1, output, arr)
After Merge:
[1, 5, 7, 8, 9, 15, 17, 18, 0, 0, 0, 0] # after merge(0, 1, output)
After writing to output:
[1, 5, 7, 8, 9, 15, 17, 18, 1, 4, 7, 7] # after divide(2, 2, output, arr)
After Merge:
[1, 1, 4, 5, 7, 7, 7, 8, 9, 15, 17, 18] # after merge(0, 2, output)