2
정렬 된 부분을 유지하기위한 추가 배열을 만들지 않고 코드 병합을 시도했습니다. 오류가 발생하여 몇 시간 후에 배열의 마지막 비트가 잘못된 순서로 정렬됩니다 . . 프로그래머 꽤 도우미 메서드, 나는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