Mergesort

Java/Collection 2012.01.27 15:10 |

샘플 코드:

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];
mergesort(0, number - 1);
}
private void mergesort(int low, int high) {
// check if low is smaller then high, if now 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 static void printResult(int[] numbers) {
for (int i = 0; i < numbers.length; i++) {
System.out.print(" "+numbers[i]);
}
System.out.println();
}
private static boolean validate(int[] numbers) {
for (int i = 0; i < numbers.length - 1; i++) {
if (numbers[i] > numbers[i + 1]) {
return false;
}
}
return true;
}
public static void main(String[] args) {
int[] test = { 5, 10, 6, 15, 4, 4, 5, 18, 4, 4, 2, 6, 1, 9 };
long startTime = System.currentTimeMillis();
System.out.println("startTime " + startTime);
Mergesort sorter = new Mergesort();
sorter.sort(test);
long stopTime = System.currentTimeMillis();
System.out.println("stopTime " + stopTime);
long elapsedTime = stopTime - startTime;
System.out.println("Mergesort " + elapsedTime);
if (!validate(test)) {
System.out.println("Should not happen");
}
printResult(test);
}
}





신고

'Java > Collection' 카테고리의 다른 글

Mergesort  (0) 2012.01.27
Quicksort  (0) 2012.01.27
LinkedList class  (0) 2012.01.19
ArrayList class  (0) 2012.01.19
Posted by jeonguk