アルゴリズムソートの難題1

import java.io.*;
import java.util.*;
import java.io.IOException;
import java.util.Scanner;

public class HW1 {

	public static void main(String[] args) throws IOException {
		String name;
		Scanner sc = new Scanner(System.in);
		System.out.println("입력 파일 이름?");
		name = sc.next();

		FileReader fr = new FileReader(name);
		BufferedReader br = new BufferedReader(fr);

		int cnt = 0;
		int ck = 0;
		String str = "";

		String[] array = new String[48469];
		String[] Selectionarray = new String[48469];
		String[] Insertionarray = new String[48469];
		String[] Shellarray = new String[48469];
		String[] MergeTDarray = new String[48469];
		String[] MergeBUarray = new String[48469];
		
		try {
			while ((str = br.readLine()) != null) {
				StringTokenizer st = new StringTokenizer(str);
				cnt += st.countTokens();
				while (st.hasMoreTokens()) {
					array[ck++] = st.nextToken();
				}
			}

			for (int i = 0; i < array.length; i++) {
				Selectionarray[i] = array[i];
				Insertionarray[i] = array[i];
				Shellarray[i] = array[i];
				MergeTDarray[i] = array[i];
				MergeBUarray[i] = array[i];
			}

			long Selectionstart = System.currentTimeMillis();
			Selection.sort(Selectionarray);
			long SelectionendTime = System.currentTimeMillis();

			long Insertionstart = System.currentTimeMillis();
			Insertion.sort(Insertionarray);
			long InsertionendTime = System.currentTimeMillis();

			long Shellstart = System.currentTimeMillis();
			Shell.sort(Shellarray);
			long ShellendTime = System.currentTimeMillis();

			long Mergestart = System.currentTimeMillis();
			MergeTD.sort(MergeTDarray);
			long MergeTDendTime = System.currentTimeMillis();
			
			long MergeBUstart = System.currentTimeMillis();
			MergeTD.sort(MergeBUarray);
			long MergeBUendTime = System.currentTimeMillis();
			
			System.out.println("1. 단어의 수 : " + cnt);
			System.out.println("2. 선택정렬: 정렬 여부 = " + Selection.isSorted(Selectionarray) + " , 소요 시간 = "
					+ (SelectionendTime - Selectionstart) + "ms");
			System.out.println("3. 삽입정렬: 정렬 여부 = " + Insertion.isSorted(Insertionarray) + " , 소요 시간 = "
					+ (InsertionendTime - Insertionstart) + "ms");
			System.out.println("4. Shell정렬: 정렬 여부 = " + Shell.isSorted(Shellarray) + " , 소요 시간 = "
					+ (ShellendTime - Shellstart) + "ms");
			System.out.println("5. Top Down 합병정렬: 정렬 여부 = " + MergeTD.isSorted(MergeTDarray) + " , 소요 시간 = "
					+ (MergeTDendTime - Mergestart) + "ms");
			System.out.println("6. Bottom Up 합병정렬: 정렬 여부 = " + MergeBU.isSorted(MergeBUarray) + " , 소요 시간 = "
					+ (MergeBUendTime - MergeBUstart) + "ms");
			
		} catch (Exception ex) {
			ex.printStackTrace();
		}
		br.close();
		fr.close();
	}
}

abstract class AbstractSort {
	public static void sort(Comparable[] a) {
	};

	protected static boolean less(Comparable v, Comparable w) {
		return v.compareTo(w) < 0;
	}

	protected static void exch(Comparable[] a, int i, int j) {
		Comparable t = a[i];
		a[i] = a[j];
		a[j] = t;
	}

	protected static void show(Comparable[] a) {
		for (int i = 0; i < a.length; i++) {
			System.out.println(a[i]);
		}
	}

	protected static boolean isSorted(Comparable[] a) {
		for (int i = 1; i < a.length; i++)
			if (less(a[i], a[i - 1]))
				return false;
		return true;
	}
}

class Selection extends AbstractSort {
	public static void sort(Comparable[] a) {
		int N = a.length;
		for (int i = 0; i < N - 1; i++) {
			int min = i;
			for (int j = i + 1; j < N; j++) {
				if (less(a[j], a[min]))
					min = j;
			}
			exch(a, i, min);
		}
		assert isSorted(a);
	}
}

class Insertion extends AbstractSort {
	public static void sort(Comparable[] a) {
		int N = a.length;
		for (int i = 1; i < N; i++) {
			for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
				exch(a, j, j - 1);
			}
		}
		assert isSorted(a);
	}
}

class Shell extends AbstractSort {
	public static void sort(Comparable[] a) {
		int N = a.length;
		int h = 1;
		while (h < N / 3)
			h = 3 * h + 1;
		while (h >= 1) {
			for (int i = h; i < N; i++)
				for (int j = i; j >= h && less(a[j], a[j - h]); j -= h)
					exch(a, j, j - h);
			h /= 3;
		}
	}
}

class MergeTD extends AbstractSort {

	private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
		for (int k = lo; k <= hi; k++)
			aux[k] = a[k];

		int i = lo, j = mid + 1;
		for (int k = lo; k <= hi; k++) {
			if (i > mid)
				a[k] = aux[j++];
			else if (j > hi)
				a[k] = aux[i++];
			else if (less(aux[j], aux[i]))
				a[k] = aux[j++];
			else
				a[k] = aux[i++];
		}
	}

	public static void sort(Comparable[] a) {
		Comparable[] aux = new Comparable[a.length];
		sort(a, aux, 0, a.length - 1);
	}

	private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
		if (hi <= lo)
			return;
		int mid = lo + (hi - lo) / 2;
		sort(a, aux, lo, mid);
		sort(a, aux, mid + 1, hi);
		merge(a, aux, lo, mid, hi);
	}
}

class MergeBU extends AbstractSort {
	private static void merge(Comparable[] in, Comparable[] out, int lo, int mid, int hi) {
		int i = lo, j = mid + 1;
		for (int k = lo; k <= hi; k++) {
			if (i > mid)
				out[k] = in[j++];
			else if (j > hi)
				out[k] = in[i++];
			else if (less(in[j], in[i]))
				out[k] = in[j++];
			else
				out[k] = in[i++];
		}
	}

	public static void sort(Comparable[] a) {
		Comparable[] src = a, dst = new Comparable[a.length], tmp;
		int N = a.length;
		for (int n = 1; n < N; n *= 2) { 
			for (int i = 0; i < N; i += 2*n) 
				merge(src, dst, i, i+n-1, Math.min(i+2*n-1, N-1));
		}
		if (src != a) System.arraycopy(src, 0, a, 0, N);
	}
}

결과

입력 파일 이름?
la.txt
1. 단어의 수 : 48469
2. 선택정렬: 정렬 여부 = true , 소요 시간 = 8038ms
3. 삽입정렬: 정렬 여부 = true , 소요 시간 = 6960ms
4. Shell정렬: 정렬 여부 = true , 소요 시간 = 41ms
5. Top Down 합병정렬: 정렬 여부 = true , 소요 시간 = 74ms
6. Bottom Up 합병정렬: 정렬 여부 = true , 소요 시간 = 21ms