среда, 1 августа 2012 г.

algorithm: sorted array merging



АЛГОРИТМ: слияние отсортированных массивов.


"Недоделанный" код, слияния отсортированных массивов
import java.util.Arrays;

public class Merger {
    public static int[] merge(int[] a, int[] b) { // wrong!
        int[] result = new int[a.length + b.length];
        int aIndex = 0;
        int bIndex = 0;
        while (aIndex + bIndex != result.length) {
            if (a[aIndex] < b[bIndex]) {
                result[aIndex + bIndex] = a[aIndex++];
            } else {
                result[aIndex + bIndex] = b[bIndex++];
            }
        }
        return result;
    }
}

и "тестирующий" его класс:
class TestMerge {
    public static void main(String[] args) {
        int[][][] data = {
                {{}, {}},
                {{0}, {}},
                {{}, {0}},
                {{0}, {0}},
                {{0, 2}, {1, 3}},
                {{0, 2, 7, 9, 123}, {1, 3, 4, 5, 6}},
        };
        for (int[][] origin : data) {
            int[] left = origin[0];
            int[] right = origin[1];
            int[] merged = Merger.merge(left, right);
            System.out.println(
                    Arrays.toString(left) +
                    " + " +
                    Arrays.toString(right) +
                    " -> " +
                    Arrays.toString(merged));
            System.out.println();
        }
    }
}
Должен выводить, но не выводит
>> [] + [] -> []
>> [0] + [] -> [0]
>> [] + [0] -> [0]
>> [0] + [0] -> [0, 0]
>> [0, 2] + [1, 3] -> [0, 1, 2, 3]
>> [0, 2, 7, 9, 123] + [1, 3, 4, 5, 6] -> [0, 1, 2, 3, 4, 5, 6, 7, 9, 123]
-- Примечание: 
Это часть рекурсивного алгоритма "сортировка слиянием" (Merge Sort), с ней можно познакомиться на странице.



    Лабораторные
    Задания лабораторных можно прочитать на этой странице.
    К этой странице относится лабораторная array_merger_fixed proc.loop.array_merger_fixed.