기초: Merge Sort

도서관 관리 프로그램에서 필요한 기능을 구현하는 것 보다 기능 자체를 떠올리는 데 시간을 더 쓰면서

실제로 기능을 구현하는 데는 시간을 거의 쓰지 못하고 있었다.

그러던 차에 그냥 연습문제를 풀어보는 것이 나을 것 같아서 기본적인 Sorting프로그램을 하나 짜 보았다.

연달아, 며칠 동안 작성한 예제 한두 개를 더 포스팅하려 한다.

아래는 merge sort의 코드.

public class Sort {
	int[] theList;
	
	public Sort(int[] inputList) {
		theList=sort(inputList);
	}
	
	public int[] sort(int[] inputList) {
		if(inputList.length<2)
			return inputList;
		else {
			return merge(sort(split(inputList).firstList),sort(split(inputList).secondList));
		}
	}
	
	
	class ListTuple{
		int[] firstList;
		int[] secondList;
		
		public ListTuple(int[] list1, int[] list2) {
			firstList=list1;
			secondList=list2;
		}
	}
	
	public ListTuple split(int[] list) {
		int lengthOfInput=list.length;
		int i=0; //counter
		int[] list1=new int[lengthOfInput/2], list2=new int[lengthOfInput-lengthOfInput/2];
		for(int temp:list) {
			if(i<(int)(lengthOfInput/2))
				list1[i]=temp;
			else
				list2[i-lengthOfInput/2]=temp;
			i++;
		}
		return new ListTuple(list1, list2);
	}
	
	public int[] merge(int[] list1, int[] list2) {
		int length=list1.length+list2.length;
		int[] result=new int[length];
		for(int i=0, j=0;i+j<length;){
			if(i==list1.length) {
				for(;j<list2.length;){
					result[i+j]=list2[j];
					j++;
				}
				break;
			}
			if(j==list2.length) {
				for(;i<list1.length;) {
					result[i+j]=list1[i];
					i++;
				}
				break;
			}
			
			if(list1[i]<list2[j]) {
				result[i+j]=list1[i];
				i++;
			}
			else {
				result[i+j]=list2[j];
				j++;
			}
		}
		return result;
	}
	
	public int[] merge(ListTuple tuple) {
		return merge(tuple.firstList,tuple.secondList);
	}
	
	public static void main(String[] args) {
		int length=100;
		int[] unSortedList=new int[length];
		int i=0;
		
		System.out.println("정렬 전 리스트");
		for(i=0;i<length;i++) {
			unSortedList[i]=(int)(100*Math.random());
			System.out.printf("%d ", unSortedList[i]);
		}
		System.out.println(" ");
		
		int[] sortedList=new Sort(unSortedList).theList;
		
		System.out.println("정렬 후 리스트");
		for(i=0;i<length;i++)
			System.out.printf("%d ",sortedList[i]);
	}

}