arraylistマージソートのバグを見つけるのに役立つ

Question

私は文字列のarraylistsのマージソートアルゴリズムを実装しようとしていますが、私はarraylistの順序をねじっているバグを見つけることができないようです。

private static void sort(java.util.ArrayList<String> a) 
{ 

    // End recursion 
    if (a.size() < 2) 
    { 
     return; 
    } 


    int mid = a.size()/2; 


    java.util.ArrayList<String> left = new java.util.ArrayList<String>(); 


    int i; 

    for (i = 0; i < mid; i++) 
    { 

     left.add(a.remove(i)); 

    } 


    java.util.ArrayList<String> right = new java.util.ArrayList<String>(); 

    // Copy the second half to the "right" 
    for (; i < a.size(); i++) 
    { 
     right.add(a.remove(i)); 
    } 


    sort(left); 
    sort(right); 

    merge(a, left, right); 
} 

private static void merge(java.util.ArrayList<String> result, java.util.ArrayList<String> left,java.util.ArrayList<String> right) 
{ 
    int i, l, r; 

    i = l = r = 0; 


    while (l < left.size() && r < right.size()) 
    { 
     if ((left.get(l)).compareTo(right.get(r)) < 0) 
     { 
     result.add(left.get(l)); 
     l++; 
     } 
     else 
     { 
     result.add(right.get(r)); 
     r++; 
     } 

     i++; 
    } 


    while (l < left.size()) 
    { 
     result.add(left.get(l)); 
     l++; 
     i++; 
    } 

    // Append rest of the values in the right half, if any... 
    while (r < right.size()) 
    { 
     result.add(right.get(r)); 
     r++; 
     i++; 
    } 
} 

Answer 1

問題はsortの機能です。

a.remove(i)を使用するとどうなりますか？インデックスiの要素が配列から削除されるため、以前にインデックスi+1にあった要素がインデックスiになり、配列のサイズが減少します。 i++を実行してからa.remove(i)を再度実行すると、配列内の1つの要素がスキップされます。

sort関数では、mergeを呼び出すときは、a.size() == 0をチェックする必要があります。必ずしもそうではないことがわかります。 merge関数はうまく見えますが、配列の分割が間違っています：remove(int i)を使用して配列が変更されていることを忘れています。その大きさとその要素のインデックスを示します。