MergeSortのステップバイステッププロセスを印刷するには

Question

MergeSortの印刷に問題があります。私は、ArrayListをソートする際に、各ステップをステップ・プロセスで印刷する手助けが必要です。

11 79 60 45 START

：私はそれはArrayListの中に2つの要素を入れ替え毎に一度に印刷あったとして

次の例では、挿入ソートからのものです11 60 79 45

11 45 60 79 FINISH

は、STからの配列全体を示しながらマージソートのためにこれを行うには、とにかくあり終了する芸術（上記のような？）

コード：

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

あなたのコードを見て、正確に知るのは難しいですが、私はここから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(" "); 
    } 
} 

コンソールに印刷したくない場合は、出力を出力の文字列に構築し、すべて完了したらそれを返すことができます。

Answer 3

ここでは、小さなMergeソートアルゴリズムプログラムを示します。アルゴリズムを 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); 
    } 
} 

}