Shell/Merge Sort(TopDown/BottomUp) 실행시간 비교(코드첨부)

「 Shell/Merge(Top Down, Bottom UP) 소팅 알고리즘의 실행시간 비교 」

소팅방법 중 대표적인 방법인 Shell Sort / Merge Sort에 대해 알아보고, 이들에 대한 소팅 시간을 직접 계산하여 비교하는 코드에 대해 알아봅시다.

 

Merge Sort방식은 Top Down 방식과 Bottom Up 방식 두 개로 나눠 각각 비교하도록 하겠습니다.

 

「 소팅 알고리즘에 대한 이해 」

1) Shell Sort(셸 정렬)란?

셸 정렬은 삽입정렬이 어느 정도 정렬 된 배열에서는 좋은 효율을 낸다는 점에서 착안하여 삽입정렬의 문제점은 줄이고 장점을 극대화 한 알고리즘입니다.

 

간단히 말해, 삽입정렬처럼 전체 배열을 한번에 정렬하지않고, 배열을 여러개의 부분 리스트로 나누고, 각 부분을 삽입정렬을 통해 정렬하는 방식으로 동작합니다.

 

2) Merge Sort(합병 정렬)란?

합병 정렬은 분할 정복 알고리즘의 하나로써, 데이터 분포가 어떻던 간에 정렬되는 시간은 O(nlong2n)으로 안정적인 모습을 보여주는 알고리즘입니다.

 

간단히 말해, 정렬되지 않은 리스트를 각각 하나의 원소만 포함하는 n개의 부분 리스트로 분할한 후, 각 부분을 정렬하고 병합하는 방식을 반복하며 동작합니다.

 

Top Down 방식의 Merge Sort는 '정렬된 서브 배열' 2개를 만들고 병합하는 과정을 반복하여 정렬하는 방식이며, Bottom Up 방식의 Merge Sort는' 작은 서브배열'을 여러개 정렬 해 놓고, 점점 서브 배열의 수를 반씩 줄여나가며 정렬하는 방식을 뜻합니다.

 

Ex) Top Down 방식

 [18] [14] [13] [12] [13] [10] [16] [17]

 [18, 14]

 [12, 13]

 [12, 13, 14, 18]

 [10, 13]

 [16, 17]

 [10, 13, 16, 17]

 [10, 12, 13, 13, 14, 16, 17, 18]

 

Ex) Bottom Up 방식

 [18] [14] [13] [12] [13] [10] [16] [17]

 [14, 18]

 [12, 13]

 [10, 13]

 [16, 17]

 [12, 13, 14, 18]

 [10, 13, 16, 17]

 [10, 12, 13, 13, 14, 16, 17, 18]

 

아래는 각 정렬 방식에 대한 시간을 측정 해 보기 위한 기본 규칙입니다.

 

문제 기본 규칙

 - 시간을 관찰하기 위하여 동일한 A 베열을 사용 함.

 - 시간 계산은 System.currentTimeMills() 함수 사용.

 

「 Shell Sort 」

아래는 Shell Sort를 구현한 코드입니다.

public 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;
		}
		assert isSorted(a);
	}
}

 

「 Merge Sort(Top Down)」

아래는 Merge Sort(Top Down)를 구현한 코드입니다.

public 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);
		assert isSorted(a);
	}
	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);
	}
}

 

「 Merge Sort(Bottom Up) 」

아래는 Merge Sort(Bottom Up)를 구현한 코드입니다.

public 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));
			tmp=src;src=dst;dst=tmp;
		}
		if(src!=a)System.arraycopy(src, 0, a, 0, N);
		assert isSorted(a);
	}
}

 

※ 코드 실행에 필요한 파일은 첨부파일로 올려 드리겠습니다. 참고하시면 됩니다.

 

「 실행결과 및 소팅 시간 비교 」

실행결과

n을 입력 ?
10
Shell Sort : 0.003초
Top Down Merge Sort : 0.002초
Bouttom Up Merge Sort : 0.001초

---

n을 입력 ?
100
Shell Sort : 0.0초
Top Down Merge Sort : 0.001초
Bouttom Up Merge Sort : 0.0초

---

n을 입력 ?
1000
Shell Sort : 0.001초
Top Down Merge Sort : 0.001초
Bouttom Up Merge Sort : 0.001초

---

n을 입력 ?
10000
Shell Sort : 0.012초
Top Down Merge Sort : 0.028초
Bouttom Up Merge Sort : 0.008초

---

n을 입력 ?
100000
Shell Sort : 0.055초
Top Down Merge Sort : 0.04초
Bouttom Up Merge Sort : 0.059초

---

n을 입력 ?
1000000
Shell Sort : 1.16초
Top Down Merge Sort : 0.418초
Bouttom Up Merge Sort : 0.412초

---

n을 입력 ?
10000000
Shell Sort : 39.477초
Top Down Merge Sort : 7.942초
Bouttom Up Merge Sort : 5.187초

 

해당 코드로 실행 결과 n에 따른 sort시간이 위와같이 나오는것을 확인 할 수 있었습니다.

 

n의 수가 커질수록 Shell Sort와 Merge Sort의 소팅시간이 확연히 차이나는걸 눈으로 확인할 수 있습니다.

이처럼 알고리즘에 대한 이해를 바탕으로 직접 코드를 작성하고, 이에따른 시간차를 눈으로 직접 확인함으로써 시간복잡도에 대한 직관적인 이해를 할 수 있습니다.

Sort.zip

0.00MB