Как распечатать пошаговый процесс в MergeSort

Question

У меня проблемы с печатью MergeSort. Мне нужна помощь в распечатке каждого пошагового процесса, так как он сортирует ArrayList.

Следующий пример взят из InsertionSort, так как я печатал его каждый раз, когда он менял два элемента в ArrayList:

11 79 60 45 START

11 79 60 45

11 60 79 45

11 45 60 79 FINISH

Есть ли в любом случае сделать это для MergeSort при отображении всего массива от начала до конца (как выше?)

Код:

import java.util.ArrayList;

public class Merge 
{
    public static void main (String [] args) 
    {
        Merge run = new Merge();
        run.test();
    }

    public void test ( )
    {
        ArrayList<Integer> numbers = new ArrayList<Integer>();
        for (int i = 0; i < 16; i++)
        {
            numbers.add(new Integer(1 + (int)(Math.random() * 100)));
        }
        printArray(numbers);
        mergeSort(numbers);
        printArray(numbers);
    }

    public void printArray (ArrayList<Integer> array)
    {
        System.out.println("\n\n");
        for (int i = 0; i < array.size(); i++)
        {
            System.out.printf("%-5d",array.get(i).intValue());
        }
        System.out.println("\n\n");
    }

    public void mergeSort (ArrayList<Integer> array) 
    {   
        int length = array.size();
        if (length < 2)
        {
            return;  // the array is already sorted in this case
        }
        // divide
        ArrayList<Integer> array1 = new ArrayList<Integer>(); 
        ArrayList<Integer> array2 = new ArrayList<Integer>(); 
        int i = 0;

        while (i < length/2)
        {
            array1.add(array.remove(0)); // move the first n/2 elements to array1
            i++;
        }
        while (!array.isEmpty())
        {
            array2.add(array.remove(0)); // move the rest to array2
        }

        mergeSort(array1);
        mergeSort(array2);
        merge(array1,array2,array); 
    }

    public void merge (ArrayList<Integer> array1, ArrayList<Integer> array2, ArrayList<Integer> array)
    {   
        while (!array1.isEmpty() && !array2.isEmpty())
        {
            if ((array1.get(0).compareTo(array2.get(0)) <= 0))
            {
                array.add(array1.remove(0));
            }
            else
            {
                array.add(array2.remove(0));
            }
        }
        while(!array1.isEmpty()) // move the remaining elements of array1
        {
            array.add(array1.remove(0));
        }
        while(!array2.isEmpty()) // move the remaining elements of array2
        {
            array.add(array2.remove(0));
        }
    }
}

Answer 1

Если вы передали какое-то смещение mergeSort, вы можете распечатать вложенный массив с отступом в том месте, где он будет находиться в полном массиве, когда вы делаете перестановки, но так как вы передаете только части массива вниз, вы не сможете отобразить полный массив таким образом. Тем не менее, есть более быстрый способ, который позволит вам.

Вместо того, чтобы создавать новые массивы и передавать их вниз, передайте массив и 2 индекса, начальную и конечную точки. Итак, ты говоришь mergeSort(array, 0, n) для первого, затем mergeSort(array, 0, n/2) а также mergeSort(array, n/2, n) для рекурсивных вызовов. Вы делаете свое расщепление и слияние только в этих пределах. Затем при слиянии вы можете распечатать весь объединенный массив. Это будет показывать шаг при каждом слиянии. На нижнем уровне будет отображаться своп 1-1 (если это произойдет). Это единственный "шаг за шагом", который вы можете увидеть в слиянии.

Answer 2

Вот небольшая программа алгоритма сортировки слиянием. Я скопировал алгоритм с http://en.wikipedia.org/wiki/Merge_sort. Вы можете просто запустить его как JUnittest или запустить метод main.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import junit.framework.TestCase;

/**
 * Simple MergeSortTest
 */

public class MergeSortTest extends TestCase {


private static int FIRST_ENTRY = 0;

public static void main(String[] args) {
    MergeSortTest mergesorttest = new MergeSortTest();
    Integer [] unsortedInt = {1,38, 27, 110, 9, 82, 10, 100, 299, 13};
    List<Integer> unsorted = Arrays.asList(unsortedInt);
    List<Integer> sorted = mergesorttest.mergeSort(unsorted);
    System.out.println(sorted.toString());
}

public void testMergeSort() {
    Integer [] unsortedInt = {1,38, 27, 110, 9, 82, 10, 100, 299, 13};
    List<Integer> unsorted = Arrays.asList(unsortedInt);
    List<Integer> sorted = mergeSort(unsorted);
    assertEquals("[1, 9, 10, 13, 27, 38, 82, 100, 110, 299]", sorted.toString());
}

private List<Integer> mergeSort(List<Integer> list) {
    List<Integer> result;
    List<Integer> left = new ArrayList<Integer>();
    List<Integer> right = new ArrayList<Integer>();;
    int middle;
    int counter;
    if (list.size() <= 1) {
        return list;
    }
    middle = list.size() / 2;

    for (counter = 0; counter < middle; counter++)  {
        left.add(list.get(counter));
    }

    for (counter = middle; counter < list.size(); counter++)  {
        right.add(list.get(counter));
    }   

    left = mergeSort(left);
    right = mergeSort(right);
    result = merge(left, right);
    System.out.println(result);
    return result;
}

private List<Integer> merge(List<Integer> left, List<Integer> right) {
    List<Integer> result = new ArrayList<Integer>();
    while (!left.isEmpty() || !right.isEmpty()) {
        if (!left.isEmpty() && !right.isEmpty()) {
            if (left.get(FIRST_ENTRY) <= right.get(FIRST_ENTRY)) {
                handle(left, result);
            } else {
                handle(right, result);
            }
        } else if (!left.isEmpty()) {
            handle(left, result);
        } else if (!right.isEmpty()) {
            handle(right, result);
        }
    }
    return result;  
}

private void handle(List<Integer> list, List<Integer> result) {
    if (!list.isEmpty()) {
        result.add(list.get(FIRST_ENTRY));
        list.remove(FIRST_ENTRY);
    }
}

}

Answer 3

Из-за того, что вы не видите ваш код, трудно точно знать, но я взял реализацию Mergesort отсюда: http://www.vogella.de/articles/JavaAlgorithmsMergesort/article.html.
Я обновил его, чтобы распечатать, как вы хотите.

public class Mergesort 
{
    private int[] numbers;
    private int[] helper;

    private int number;

    public void sort(int[] values) 
    {
        this.numbers = values;
        number = values.length;
        this.helper = new int[number];

        System.out.println("START");

        mergesort(0, number - 1);

        System.out.println("END");
    }

    private void mergesort(int low, int high) 
    {
        // Check if low is smaller then high, if not then the array is sorted
        if (low < high) 
        {
            // Get the index of the element which is in the middle
            int middle = (low + high) / 2;
            // Sort the left side of the array
            mergesort(low, middle);
            // Sort the right side of the array
            mergesort(middle + 1, high);
            // Combine them both
            merge(low, middle, high);
        }
    }

    private void merge(int low, int middle, int high) 
    {

        // Copy both parts into the helper array
        for (int i = low; i <= high; i++) 
        {
            helper[i] = numbers[i];
        }

        int i = low;
        int j = middle + 1;
        int k = low;

        // Copy the smallest values from either the left or the right side back
        // to the original array
        while (i <= middle && j <= high) 
        {
            if (helper[i] <= helper[j]) 
            {
                numbers[k] = helper[i];
                i++;
            } 
            else 
            {
                numbers[k] = helper[j];
                j++;
            }
            k++;
        }

        // Copy the rest of the left side of the array into the target array
        while (i <= middle) 
        {
            numbers[k] = helper[i];
            k++;
            i++;
        }

    }

    private void printArray()
    {
        for(int x : numbers)
            System.out.print(x + " ");

        System.out.println(" ");
    }
}

Если вы не хотите печатать на консоль, вы можете построить вывод в строку вывода и вернуть его, когда все будет готово.