2
ソートされた部分を保持するための追加の配列を作成せずにマージソートをコードしようとしましたが、数時間後にエラーが見つからず、配列の最後のビットが間違った順序でソートされます。 Theresのかなりの数のヘルパーメソッド、私はそれらを左に、デバッグに使用Java、マージソート
public class Sorter2
{
public static void toString(int [] list)
{
for(int i = 0; i < list.length; i++)
{
System.out.print(list[i]);
if(!(i + 1 == list.length))
{
System.out.print(",");
}
}
System.out.println("");
}
public static void toString(int list[], int from, int to)
{
for(int i = from; i <= to; i++)
{
System.out.print(list[i]);
if(i + 1 <= to)
{
System.out.print(",");
}
}
System.out.println("");
}
public static void insertAt(int [] list, int insert_at, int taken_from)
{
int to_insert = list[taken_from];
for(int i = taken_from; i >= insert_at; i--)
{
if(i != insert_at)
{
list[i] = list[i - 1];
}
else
{
list[i] = to_insert;
}
}
}
public static void sortSegments(int [] list ,int segment_one_begin, int segment_one_end, int segment_two_begin, int segment_two_end)
{
toString(list, segment_one_begin, segment_two_end);
int sorted = 0;
for(int i = segment_two_begin; i <= segment_two_end; i++)
{
for(int l = segment_one_begin + sorted; l <= segment_one_end; l++)
{
if(list[i] <= list[l])
{
insertAt(list, l, i);
sorted++;
}
}
}
toString(list, segment_one_begin, segment_two_end);
}
public static void mergeSort(int [] list, int segment_begining, int segment_end)
{
if(segment_end - segment_begining < 1)
{
return;
}
else
{
int midpoint = (segment_end + segment_begining)/2;
mergeSort(list, segment_begining, midpoint);
mergeSort(list, midpoint + 1, segment_end);
sortSegments(list, segment_begining, midpoint, midpoint + 1, segment_end);
}
}
public static void mergeSort(int [] list)
{
mergeSort(list, 0, list.length - 1);
}
public static boolean isInOrder(int [] toCheck)
{
for(int i = 1; i < toCheck.length; i++)
{
if(toCheck[i] < toCheck[i - 1])
{
return false;
}
}
return true;
}
public static int [] populate(int numOfItems)
{
int [] toReturn = new int[numOfItems];
for(int i = 0; i < toReturn.length; i++)
{
toReturn[i] = (int) (Math.random() * 100 + 1);
}
return toReturn;
}
public static void main(String [] args)
{
int [] nums = populate(20);
mergeSort(nums);
toString(nums);
System.out.println(isInOrder(nums));
}
}
ここではマージソートの実装を探す：http://www.vogella.de/articles/JavaAlgorithmsMergesort/article.html – Wilmer
これは宿題であれば、そのようにタグを付けてください。 –
いいえ、それは私の宿題ではありません。 – foFox