정렬 알고리즘 정리 [C++][C#]

SJ.Lee·2021년 9월 27일
1

알고리즘

목록 보기
1/1

정렬이란?

정렬(sorting)은 이름, 학번, 키 등 핵심 항목의 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업을 말합니다. 정렬을 하면 검색을 더 쉽게 할 수 있게 됩니다.
정렬에는 두 가지 종류가 있는데 안정 정렬과 불안정 정렬이 있습니다.
안정 정렬은 배열 내의 중복된 요소를 입력 순서와 동일하게 정렬하는 알고리즘들을 말합니다. 이 포스팅에서 소개할 정렬 알고리즘 중 안정 정렬은 버블 정렬, 병합 정렬이 있습니다.
불안정 정렬은 안정 정렬과 반대로 중복된 요소가 입력 순서와 동일하게 정렬되지 않는 알고리즘들입니다. 여기서 소개할 정렬 알고리즘 중에서는 퀵 정렬, 힙 정렬, 계수 정렬이 이에 해당합니다.


swap 메소드

기본적으로 아래의 정렬들에서 쓸 swap 메소드를 미리 정의하겠습니다.
[C#]

static void Swap(int[] arr, int a, int b){
    int tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
}

C++에서는 algorithm 라이브러리에 swap 함수가 구현되어 있습니다.
추가적인 복제가 발생하지 않도록 하기 위해 이동 의미론을 적용해서 구현되어 있습니다. 이동 의미론에 대해서는 나중에 기회가 된다면 따로 글을 올리도록 하겠습니다. algorithm 라이브러리에 있는 swap 함수는 다음과 같이 구현되어 있습니다.
[C++]

void swap(T& a, T& b){
    T temp(std::move(a));
    a = std::move(b);
    b = std::move(temp);
 }

버블 정렬

O(n2) 시간에 동작

이웃한 두 요소의 대소 관계를 비교하여 교환을 반복하는 정렬 방법

기본 코드

요소의 개수가 n개인 배열에서 n-1회 비교, 교환을 하고 나면 가장 작은 요소가 맨 처음으로 이동하는데, 이런 일련의 비교, 교환 과정을 '패스'라고 합니다.
패스마다 a[j-1]과 a[j]를 비교해서 앞쪽이 크면 교환하는 과정을 진행합니다. 이렇게 한 패스가 끝나면 가장 앞에 있는 요소는 그 배열에서 가장 작은 요소가 되므로 패스를 k회 수행하면 앞쪽의 요소 k개가 정렬된다는 것을 알 수 있습니다. 따라서 모든 정렬이 끝나려면 n-1회의 패스가 수행되어야 합니다.
[C#]

static void BubbleSort(int[] a, int n){
    for(int i = 0; i < n-1; i++){
    	for(int j = n-1; j > i; j--){
        	if(a[j-1] > a[j]) Swap(a, j-1, j);
        }
    }
}

[C++]

void bubbleSort(int* a, int n){
    for(int i = 0; i < n-1; i++){
        for(int j = n-1; j > i; j--){
            if(a[j-1] > a[j]) std::swap(a[j-1], a[j]);
        }
    }
}

알고리즘 개선

각각의 패스에서 비교, 교환을 하다가 어떤 시점 이후에 교환이 수행되지 않는다면 그보다 앞쪽의 요소는 이미 정렬을 마친 상태라고 생각해도 무방합니다. 따라서 마지막으로 요소를 교환한 위치를 저장한 다음에, 다음 패스에서 그 위치까지만 비교, 교환을 수행하면 알고리즘을 개선할 수 있습니다.
[C#]

static void BubbleSort(int[] a, int n){
    int k = 0;
    while(k < n-1){
    	int last = n-1;
        for(int j = n-1; j > k; j--){
            if(a[j-1] > a[j]){
                Swap(a, j-1, j);
                last = j;
            }
        }
        k = last;
    }
}

[C++]

void bubbleSort(int* a, int n){
    int k = 0;
    while(k < n-1){
        int last = n-1;
        for(int j = n-1; j > k; j--){
            if(a[j-1] > a[j]){
                std::swap(a[j-1], a[j]);
                last = j;
            }
        }
        k = last;
    }
}

병합 정렬

O(nlogn) 시간에 동작

배열의 앞부분을 병합 정렬로 정렬하고 배열의 뒷부분을 병합 정렬로 정렬해서 마지막으로 배열의 앞부분과 뒷부분을 병합합니다. 따라서 재귀가 사용됩니다.
[C#]

class MergeSort{

    static int[] buff;

    static void __MergeSort(int[] a, int left, int right){
        if(left < right){
            int i, center = (left + right) / 2;
            int p = 0, j = 0, k = left;

            __MergeSort(a, left, center);
            __MergeSort(a, center+1, right);

            for(i = left; i <= center; i++) buff[p++] = a[i];
            while(i <= right && j < p) a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];
            while(j < p) a[k++] = buff[j++];
        }
    }

    static void MergeSort(int[] a, int n){
        buff = new int[n];
        __MergeSort(a, 0, n-1);
        buff = null;
    }
}

[C++]

int* buff;

void __mergeSort(int* a, int left, int right){
    if(left < right){
        int i, center = (left+right) / 2;
        int p = 0, j = 0, k = left;

        __mergeSort(a, left, center);
        __mergeSort(a, center+1, right);

        for(i = left; i <= center; i++) buff[p++] = a[i];
        while(i <= right && j < p) a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];
        while(j < p) a[k++] = buff[j++];
    }
}

void mergeSort(int* a, int n){
    buff = new int[n];
    __mergeSort(a, 0, n-1);
    delete [] buff;
    buff = nullptr;
}

퀵 정렬

O(nlogn) 시간에 동작, 최악의 경우에는 O(n2) 시간에 동작

일반적으로 사용되고 있는 아주 빠른 정렬 알고리즘입니다. 2개의 그룹을 나누는 기준인 피벗을 정하고, 피벗 값 이하의 요소를 배열 왼쪽으로, 이상의 요소를 배열 오른쪽으로 옮겨야 합니다. 그렇게 하기 위해서 아래의 작업을 먼저 수행합니다.
피벗을 x, 왼쪽 끝 요소의 인덱스 pl을 왼쪽 커서, 오른쪽 끝 요소의 인덱스 pr을 오른쪽 커서라고 할 때
1. a[p1] > x가 성립하는 요소를 찾을 때까지 pl을 오른쪽으로 스캔
2. a[pr] < x가 성립하는 요소를 찾을 때까지 pr을 왼쪽으로 스캔
스캔이 완료되면 a[pl]과 a[pr]의 값을 교환하고 다시 스캔을 진행합니다. 스캔을 진행하다보면 pl과 pr이 교차하는 지점이 나오는데, 그 지점으로 나뉘는 두 개의 그룹을 가지고 다시 퀵 정렬을 시작합니다.

이 알고리즘이 빠른 정렬 알고리즘이기는 하나 최악의 경우 O(n2) 시간에 동작할 수도 있습니다. 값이 이미 정렬되어 있다던가 역순으로 정렬된 경우, 패스마다 모든 요소를 탐색해야 하므로 O(n2) 시간에 동작하게 됩니다. 그러나 정렬을 할 때 이런 경우는 거의 없으므로 보통은 O(nlogn) 시간이 걸립니다.
[C#]

static void QuickSort(int[] a, int left, int right){
    int pl = left;
    int pr = right;
    int x = a[(pl+pr) / 2];
    
    do{
    	while(a[pl] < x) pl++;
        while(a[pr] > x) pr--;
        if(pl <= pr) Swap(a, pl++, pr--);
    } while(pl <= pr);
    
    if(left < pr) QuickSort(a, left, pr);
    if(pl < right) QuickSort(a, pl, right);
 }

[C++]

void quickSort(int* a, int left, int right){
   int pl = left;
   int pr = right;
   int x = a[(pl+pr)/2];

   do{
       while(a[pl] < x) pl++;
       while(a[pr] > x) pr--;
       if(pl <= pr) std::swap(a[pl++], a[pr--]);
   } while(pl <= pr);

   if(left < pr) quickSort(a, left, pr);
   if(pl < right) quickSort(a, pl, right);
}

비재귀적인 퀵 정렬

재귀는 함수를 호출하기 때문에 직관적이기는 하지만 비재귀에 비해 시간 성능이 저하됩니다. 따라서 재귀 버전의 퀵 정렬을 비재귀로 바꾸면 다음과 같습니다.
[C#]

static void QuickSort(int[] a, int left, int right){
    Stack<int> lstack = new Stack<int>(right - left + 1);
    Stack<int> rstack = new Stack<int>(right - left + 1);
    
    lstack.Push(left);
    rstack.Push(right);
    
    while(lstack.Count != 0){
    	int pl = left = lstack.Pop();
       int pr = right = rstack.Pop();
       int x = a[(left+right) / 2];
       
       do{
           while(a[pl] < x) pl++;
           while(a[pr] > x) pr--;
           if(pl <= pr) Swap(a, pl++, pr--);
       } while(pl <= pr);
       
       if(left < pr){
           lstack.Push(left);
           rstack.Push(pr);
       }
       if(pl < right){
           lstack.Push(pl);
           rstack.Push(right);
       }
   }
}

[C++]

void quickSort(int* a, int left, int right){
    std::stack<int> lstack;
    std::stack<int> rstack;
    lstack.push(left);
    rstack.push(right);

    while(!lstack.empty()){
        int pl = left = lstack.top(); lstack.pop();
        int pr = right = rstack.top(); rstack.pop();
        int x = a[(left+right)/2];

        do{
            while(a[pl] < x) pl++;
            while(a[pr] > x) pr--;
            if(pl <= pr) std::swap(a[pl++], a[pr--]);
        } while(pl <= pr);

        if(left < pr){
            lstack.push(left);
            rstack.push(pr);
        }
        if(pl < right){
            lstack.push(pl);
            rstack.push(right);
        }
    }
}

힙 정렬

O(nlogn) 시간에 동작

힙(heap)을 사용하는 정렬 방법입니다. 힙은 '부모의 값이 자식의 값보다 항상 크다'(또는 그 반대)는 조건을 만족하는 완전이진트리를 말합니다. 여기서 가장 큰 값이 루트에 위치한다는 특징을 이용하여 정렬을 수행하는 것이 힙 정렬입니다.
downheap 메소드를 사용하여 a[left] ~ a[right]의 요소를 힙으로 만들고 루트(a[0])에 있는 가장 큰 값을 빼내어 배열 마지막 요소와 바꾸고 배열의 나머지 부분을 다시 힙으로 만드는 과정을 반복하여 정렬을 수행합니다.
HeapSort 함수에서 처음에 DownHeap을 수행할 때 left에 해당하는 i 인자를 (n-1)/2로 한 이유는 힙이 완전이진트리이므로 노드의 개수의 절반이 리프 노드의 부모 노드이기 때문입니다.
[C#]

static void DownHeap(int[] a, int left, int right){
    int tmp = a[left];
    int child, parent;
    
    for(parent = left; parent < (right+1) / 2; parent = child){
        int cl = parent*2+1;
        int cr = cl+1;
        child = (cr <= right && a[cr] > a[cl]) ? cr : cl;
        if(tmp >= a[child]) break;
        a[parent] = a[child];
    }
    a[parent] = tmp;
}

static void HeapSort(int[] a, int n){
    for(int i = (n-1)/2; i >= 0; i--) DownHeap(a, i, n-1);
    
    for(int i = n-1; i > 0; i--){
        Swap(a, 0, i);
        DownHeadp(a, 0, i-1);
    }
}

[C++]

void downHeap(int* a, int left, int right){
    int tmp = a[left];
    int child, parent;

    for(parent = left; parent < (right+1)/2; parent = child){
        int cl = parent*2+1;
        int cr = cl+1;
        child = (cr <= right && a[cr] > a[cl]) ? cr : cl;
        if(tmp >= a[child]) break;
        a[parent] = a[child];
    }
    a[parent] = tmp;
}

void heapSort(int* a, int n){
    for(int i = (n-1)/2; i >= 0; i--) downHeap(a, i, n-1);

    for(int i = n-1; i > 0; i--){
        std::swap(a[0], a[i]);
        downHeap(a, 0, i-1);
    }
}

계수 정렬

O(n) 시간에 동작, 최악의 경우에는 O(n2) 시간에 동작

배열에서 각 숫자가 몇 번 들어가는지를 이용하는 정렬 방법입니다. 먼저 각 숫자가 몇 번 들어가는지를 세어 주고 이 횟수를 누적 합 배열로 만들어줍니다. 그리고 나서 처음 수열을 역순으로 살펴보면서 누적 합 배열과 비교하며 자리를 찾아갑니다. 원소의 값이 크면 클수록 퀵 정렬이나 힙 정렬이 더 빠릅니다. 원소의 값이 클수록 배열의 길이 자체가 커지기 때문입니다. 따라서 원소의 값이 작은 것들로 이루어진 경우에만 사용하는 것이 좋습니다.
[C#]

static int[] CountingSort(int[] a, int n, int max){
    int[] tmp = new int[max+1];
    int[] result = new int[n];
    
    for(int i = 0; i < n; i++) tmp[a[i]]++;
    for(int i = 1; i < tmp.Length; i++) tmp[i] += tmp[i-1];
    for(int i = n-1; i >= 0; i--) result[--tmp[a[i]]] = a[i];
    
    return result;
}

[C++]

void countingSort(int* a, int n, int max){
    int* tmpArr = new int[max+1]{};
    int* result = new int[n]{};

    for(int i = 0; i < n; i++) tmpArr[a[i]]++;
    for(int i = 1; i <= max; i++) tmpArr[i] += tmpArr[i-1];
    for(int i = n-1; i >= 0; i--) result[--tmpArr[a[i]]] = a[i];
    
    for(int i = 0; i < n; i++) a[i] = result[i];
    delete [] result;
    delete [] tmpArr;
}
profile
프로그래밍 / 게임 개발을 공부하고 있습니다.

0개의 댓글