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

algorithm: merge-sort

АЛГОРИТМ: сортировка слиянием
Сортировка слиянием:
public class MergeSort {
    public static int[] sort(int[] array, int from, int len) {
        if (len == 0) {
            return new int[0];
        } else if (len == 1) {
            return new int[]{array[from]};
        } else if (len == 2) {
            if (array[from] < array[from + 1]) {
                return new int[]{array[from], array[from + 1]};
            } else {
                return new int[]{array[from + 1], array[from]};
            }
        } else {
            int[] left = sort(array, from, len / 2);
            int[] right = sort(array, from + (len / 2), len - (len / 2));
            return merge(left, right);
        }
    }
    private static int[] merge(int[] a, int[] b) {
        ...
        System.out.print(Arrays.toString(a) + " + " + Arrays.toString(b));
        System.out.println(" -> " + Arrays.toString(result));
        return result;
    }
}

Тестирующий код:

class TestMergeSort {
    public static void main(String[] args) {
        int[][] data = {
                {9, 7, 0, 3, 5, 2, 6, 1, 4, 8},
                {0, 3, 5, 2, 1, 4},
                {0, 3, 5, 2, 1},
                {0, 3, 5, 2},
                {0, 3, 5},
                {0, 3},
                {0},
                {},
        };
        for (int[] origin : data) {
            System.out.println("origin: " + Arrays.toString(origin));
            int[] sorted = MergeSort.sort(origin, 0, origin.length);
            System.out.println("sorted: " + Arrays.toString(sorted));
            System.out.println();
        }
    }
}


>> origin: [9, 7, 0, 3, 5, 2, 6, 1, 4, 8]
>> [0] + [3, 5] -> [0, 3, 5]
>> [7, 9] + [0, 3, 5] -> [0, 3, 5, 7, 9]
>> [1] + [4, 8] -> [1, 4, 8]
>> [2, 6] + [1, 4, 8] -> [1, 2, 4, 6, 8]
>> [0, 3, 5, 7, 9] + [1, 2, 4, 6, 8] -> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>> sorted: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

-- Вопросы/задания:
1*) П
ерепишите его, что бы сортировка происходила in place.
Подсказка: возможно, Вам потребуется реализовать сдвиг элементов при помощи System.arraycopy(Object src, int  srcPos, Object dest, int destPos, int length).