정렬 - 합병 정렬

퀵 정렬 알고리즘을 공부하면서 직접 코드로 짜봤었는데,

[Study] - 정렬 - 퀵 정렬

 

배열의 크기가 꽤 크면, 라이브러리에서 제공해주는 정렬과 시간차이가 꽤 나서 좀 조사해보니,

 

라이브러리에서의 배열은 정수 배열은 합병 정렬(Merge Sort)를,

실수 배열은 퀵 정렬(Quick Sort)를 행한다고 한다.

(난 원래 섞어서 쓰는 줄 알았는데. 대충 검색한거라 정확한 정보는 아님.)

 

어쨌든 합병 정렬에 대해서도 알아봤다.

https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

합병 정렬 - 위키백과, 우리 모두의 백과사전

합병 정렬도 퀵 정렬과 마찬가지로 분할 정렬 알고리즘이다.

 

수를 계속해서 한 개 단위가 될 때 까지 나눈 후, 나눈 애들끼리 정렬하면서 다시 조립된다고 보면 된다.

 

나눈 애가 정렬되고 합치는 과정에서 재귀를 이용한다.

public void sortAsc(double[] origin, double[] result, int start, int end) {
    if(end>start) {
        sortAsc(origin, result, start, (end+start)/2);
        sortAsc(origin, result, (end+start)/2+1, end);
        mergeAsc(origin, result, start, end);
    }
}

public void mergeAsc(double[] origin, double[] result, int start, int end) {
    int i1 = start;
    int end1 = (end+start)/2;
    int i2 = end1+1;
    int end2 = end;
    int index = start;
    while(index<=end) {
        if(i1<=end1&&i2<=end2) {
            if(origin[i1]<=origin[i2]) result[index++] = origin[i1++];
            else result[index++] = origin[i2++];
        } else if(i1<=end1) {
            result[index++] = origin[i1++];
        } else if(i2<=end2) {
            result[index++] = origin[i2++];
        }
    }
    for(int i=start;i<=end;i++) origin[i]=result[i];
}

 

 

 

int 배열과 double 배열을 각각 1억개의 크기만큼 만든 후,

Math.random()*1000을 이용해 무작위 수를 넣고 정렬해보았다.

 

<int 배열>

퀵 정렬: 13.031999826431274 초

합병 정렬: 16.816999912261963 초

Arrays.sort(): 4.474999904632568 초

 

<double 배열>

퀵 정렬: 21.91000008583069 초
합병 정렬: 27.405999898910522 초
Arrays.sort(): 13.824000120162964 초

 

단위에 상관없이 합병 정렬보다 퀵 정렬이 빨랐다.(라이브러리보다는 한참 못 미친다.)

(으아니.. 정수와 실수로 나눠서 해본 의미가...)

 

 

이번엔 처음에 내림차순으로 되어있는 배열을 만들었다.

(내림차순→오름차순. 즉, 최악의 경우)

이 경우에는 전부 오름차순으로 바꾸기까지 시간이 꽤 걸리므로,

크기를 1억개에서 10만개로 대폭 줄였다.

 

<int 배열>

퀵 정렬: 21.236000061035156 초

합병 정렬: 0.01399993896484375 초

Arrays.sort(): 0.004999876022338867 초

 

<double 배열>

퀵 정렬: 17.59500002861023 초
합병 정렬: 0.014000177383422852 초
Arrays.sort(): 0.007999897003173828 초

 

이번엔 합병 정렬이 퀵 정렬보다 훨씬 빨랐다.

이 부분은 시간복잡도에 의한, 최악의 경우를 처리하는 퀵 정렬의 상황 때문으로 보인다.

 

합병 정렬은

최선의 경우에도, 최악의 경우에도 시간복잡도는 항상 O(n*log(n))이지만,

퀵 정렬은

최선의 경우에는 O(n*log(n))이지만, 최악의 경우에는 O(n^2)이 된다.

(그래도 평균 시간복잡도는 O(n*log(n))이긴 하다.)

 

시간복잡도는

O(1)<O(log(n))<O(n)<O(n*log(n))<O(n^2)<O(n^3)<O(2^n)<O(n!) 순으로 알고리즘 처리시간이 급격하게 증가한다.

https://namu.wiki/w/%EC%8B%9C%EA%B0%84%20%EB%B3%B5%EC%9E%A1%EB%8F%84

 

 

 

정렬에 이렇게나 많은 종류가 존재한다는 건, 역시 왕도가 없다는 소리라고 보면 되려나..

 

라이브러리와 시간차가 나는 건 정렬하면서 수를 복사했다 바꾸는 과정 같은 부분이 누적되어서 영향을 주는걸까..

 

변수 종류에 차이가 나나 봤다가 시간복잡도에 대해 공부하고 가게 되네;;