알고리즘 : 정렬 - 버블정렬, 병합정렬, 퀵정렬

정렬이란, 데이터들을 정해진 순서대로 나열하는것입니다.

알고리즘을 사용하기 위해서는 원하는 데이터가 어느위치에 있는지 알아야하는데,

정렬은 이를 도와주는 과정입니다.

 

보통 오름차순(점점 커지는 규칙)과 내림차순(점점 줄어드는 규칙)으로 구분하며,

원하는 방식을 추가로 정할수도 있습니다.

 

또한 정렬방식에 따라 시간복잡도를 아낄 수도 있습니다.

이번 글에서는 정렬 중,

버블정렬(bubble sort)

병합정렬(merge sort)

퀵정렬(quick sort) 을 알아보도록 하겠습니다.

 

 

 

 

버블정렬 (bubble sort)

버블 정렬이란, 서로 인접한 두 원소를 비교하여 위치를 변경하는 방법입니다.

인접한 두 원소를 비교하여 정렬하기 때문에, 한 사이클이 지나면 가장 크거나 작은 값이 맨 뒤로 이동합니다.

한 사이클을 유사코드로 구현하면 아래와 같습니다.

void bubble_sort_cicle( data[] arr ){
    data temp;
    for( i=0; i<arr.length; i++){
        temp = arr[i];
        arr[i] = arr[i+1];
        arr[i+1] = temp;
    }
}

 

위와같은 사이클을 배열의 개수-1 개, 총 n-1번 반복합니다.

void bubble_sort( data[] arr ){
    for( i=0;i<arr.length-1;i++){
        data temp;
        for( j=0; i<arr.length-i; j++){
            if(arr[j]>arr[j+1]){
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

 

따라서 n개의 배열의 경우 n + n-1 + n-2 + .... + 2 + 1 의 순서로 진행되며

총 시간복잡도는 어떤 경우라도 일정한 n*(n+1)/2 가 됩니다.

따라서 빅-오 표기법으로 보여주는 시간복잡도는 O(n²) 이 됩니다.

 

이러한 시간복잡도를 가지기 때문에, 어느정도 이상의 크기를 가진 데이터부터는 속도가 매우 느려지게됩니다.

 

비슷한 정렬방식으로는 선택정렬과, 삽입정렬이 존재하지만,

버블정렬과 마찬가지로 O(n²)의 시간복잡도를 가지기 때문에,

병합정렬과 같은 더 나은 정렬방식을 사용합니다.

 

 

 

 

병합정렬(merge sort)

병합 정렬은 분할정복법(divide and conquer) 을 바탕으로 한 정렬 방법으로,

데이터를 분할하고, 정렬하여 다시 합치는 방법입니다.

 

병합정렬은

리스트의 크기를 일정하게 나누는 분할

분할된 데이터를 기준에 맞게 재배치하는 정렬

정렬된 데이터를 합치는 병합으로 구성되어있습니다.

 

우선 분할은 사전에 정한 크기대로 리스트의 크기를 분할하는 것입니다.

주로 2분할을 사용하지만, 얼마나 분리할지는 사용자 재량입니다.

function divide(data[] arr, number start, number end){
    number middle = (start+end)/2;
    
    divide(arr,start,middle);
    divide(arr,middle+1,end);
}

 

이후 이렇게 나뉜 값을 정렬하고 합칩니다..

오름차순일때, 하나의 배열을 새로 만들어서 해당 배열에 작은값부터 넣습니다.

function merge(data[] array,number start, number mid, number end){
    data[] new_array = array의 값을 가진 별개의 array;
    number a,c = start;
    number b = mid+1;
    
    while(b<=end && a<=mid)
    {
         if(array[a] <= array[b]){
             new_array[c++] = array[a++];
         }
         else{
             new_array[c++] = array[b++];
         }
    }
    
    if(a<=mid){
        for(i=a;i<=mid;i++){
            new_array[k++] = array[i];
        }
    }
    else if(b<=end){
        for(i=b;i<=end;i++){
            new_array[k++] = array[i];
        }
    }
    
    // 이후 값을 복사하여 원 배열에 적용합니다.
    array = new_array;
}

 

위 두가지를 합치면 병합정렬이 완성됩니다.

 

function merge_sort(data[] arr, number start, number end){
    number middle = (start+end)/2;
    
    if(start<middle)
        merge_sort(arr,start,middle);
        
    if(middle+1<end)
        merge_sort(arr,middle+1,end);
        
    merge(arr,start,middle,end);
}

 

여기서 시간복잡도를 계산한다면,

분할과정은 위의 유사코드 기준으로 반으로 나누기때문에,
2일때는 1회,
4일때는 2회,
8일때는 3회가 됩니다

곧 나누는 횟수는 총 log₂n 회가 됩니다.

그리고 배열의 모든 데이터는 합치는 과정에서 정렬을 하므로, 한번씩 계산하게 됩니다.

 

즉 n개의 데이터는 모두 log₂n 번씩 계산을 수행한다는거죠. 따라서 병합정렬의 시간복잡도는 n log₂n 이 됩니다.

이를 빅-오 표기법으로 나타내면 O(n log n)이 됩니다.

이 과정은 배열의 값에따라 바뀌지 않기 때문에, 병합정렬의 시간복잡도는 일정합니다.

 

 

 

 

퀵 정렬 (quick sort) 

퀵 정렬은 말 그대로 빠른정렬입니다.

이 정렬의 특징은 최소시간복잡도와 최대 시간복잡도가 다르다는 점입니다.

하나의 피벗(pivot, 기준)을 정한 뒤, 피벗보다 큰 값과 작은값으로 나누어 정렬을 수행합니다.

 

function quicksort(data[] Array, number start, number end){
    number p = start;
    data pivot = p;
    data tmp;
    
    if(start==end) return;
    
    for(i=start+1, i<end;i++){
        if(Array[p]<Array[i]){
            Array[p++] = Array[i];
            Array[i] = Array[p];
            Array[p] = pivot;
        }
    }
    
    quicksort(Array, start, p-1);
    quicksort(Array, p+1, end);
}

 

이러한 과정으로 인해

피벗이 중앙에 오면 최선의 시간복잡도를 갖게 되고,

이때의 시간복잡도는 깊이 * 시행횟수로,

깊이는 log₂n 이 되고 순환 횟수는 n 이되므로 총 시간복잡도는 n log₂n 이 되어 O(log n) 이 됩니다.

 

반면, 피벗이 가장 앞이나 뒤에 있을 경우

n 회, n-1, n-2 ... 1 까지 수행을 반복하므로 n(n+1)/2 가 되어

최악 시간복잡도는 O(n²) 가 됩니다.

 

 

퀵 정렬의 장점은 이름 그대로 빠르다는 점입니다.

계산과정이 간결하여 최선시간복잡도 기준으로 O(n log n) 의 다른 정렬방법보다 빠르며,

정해진 메모리 외에 다른 메모리 소모가 없습니다.

 

단점으로는, 최악시간복잡도의 경우 O(n²) 의 시간복잡도를 가지기 때문에 매우 느려지게 됩니다.