[ Sort ] 다양한 정렬 방법

Sort Algorithm

 

데이터를 탐색하기 위해서는 데이터 공간을 어떻게 구성하는지도 중요하지만, 데이터가 어떻게 나열되어 있는지에 따라서 해를 구하는 과정이 복잡해질 수도 있고, 간단해질 수도 있다.

정렬(Sorting Algorithm)은 데이터이 주어져 있을 때, 일정한 기준으로 오름차순 또는 내림차순으로 순서를 재배열하는 것이다. 정렬이 문제 해결에서 효과적인 기법을 위해 필요하지만, 만약 정렬에서 많은 시간이 소모된다면 아무리 효율적인 문제 해결 알고리즘을 사용하더라도 전체적인 알고리즘의 성능은 떨어질 것이다. 따라서 데이터를 효율적인 시간복잡도로 정렬하는 것이 중요하다. 일반적으로 최악의 경우에 $O(N^2)$의 시간복잡도가 소모되며, 가장 효율적인 Sorting Algorithm이 보통 $O(NlogN)$으로 동작한다.

 

 

• 오름차순: $a_{1}≤a_{2}≤...≤a_{n-1}≤a_{n}$을 만족하면 오름차순이라고 한다.
• 내림차순: $a_{1}≥a_{2}≥...≥a_{n-1}≥a_{n}$을 만족하면 내림차순이라고 한다.

 

 

---

 

 

Selection Sort ( 선택 정렬 )

 

 

Selection Sort는 최솟값을 찾아 맨 앞으로 옮겨주는 방법으로, 1번 인덱스부터 시작해서 $1~N$번째 원소 중 최솟값과 1번째 원소를 바꾸고, $2~N$번째 원소 중 최솟값과 2번째 원소를 바꾸는, 즉 $i$번째 원소와 $i~N$번째 원소 중 최솟값을 바꾸는 과정을 반복해서 정렬하는 방법이다. 이 때 각 원소를 하나하나 선택해서 배치하기 때문에 시간 복잡도는 $O(N^{2})$이다.

 

 

for(int i=1; i<=n; i++){
    int idx=i;
    for(int j=i+1; j<=n; j++){
        if(v[j]<v[idx]){ idx=j; }
    }
    swap(v[i], v[idx]);
}

 

 

---

 

Bubble Sort( 버블 정렬 )

 

 

 

Bubble Sort는 인접한 두 원소를 비교하여 정렬하는 방법으로, $i$번째 원소와 $i+1$번째 원소를 비교해서 바꾸어주는 방식의 정렬 방법이다. 이 과정을 $N$번 반복하므로 시간복잡도는 $O(N^{2})$이다.

 

 

 

for(int i=1; i<=n; i++){
    bool flag=0;
    for(int j=1; j<=n-1; j++){
        if(v[j]>v[j+1]){
            swap(v[j], v[j+1]);
            flag=1;
        }
    }
    if(!flag){//더 이상 변경이 일어나지 않는다면
        break;
    }
}

 

 

---

 

Insertion Sort( 삽입 정렬 )

 

 

Insertion Sort는 이미 정렬된 부분과 비교하여 정렬하는 방법이다. 2번째 원소부터 $N$번째 원소까지 각 원소들을 key라고 했을 때, key의 위치의 앞부분과 key의 값을 비교하면서 앞부분 중 key보다 큰 부분을 뒤로 한칸씩 끌어온다. 그리고 끌어오면 빈 한 칸이 생기므로 그 부분에 key 값을 넣는다. 위 방법이 성립하는 이유는 key보다 앞에 있는 원소들은 이미 정렬되어 있는 상태이기 때문이다. 삽입 정렬의 시간복잡도는 $O(N^{2})$이다.

 

 

ex) {${5, 1, 2, 4, 3}$}

 

  1) key=arr[1]=1 -> {${  , 5, 2, 4, 3}$} -> 빈 곳에 key값을 넣는다. 

  2) key=arr[2]=2 -> {${1,   , 5, 4, 3}$} -> 빈 곳에 key값을 넣는다.

  3) key=arr[3]=4 -> {${1, 2,   , 5, 3}$} -> 빈 곳에 key값을 넣는다.

  4) key=arr[4]=3 -> {${1, 2,   , 4, 5}$} -> 빈 곳에 key값을 넣는다.

 

 

 

for(int i=2; i<=n; i++){
    int key=v[i];
    int j;
    for(j=i-1; j>=1; j--){
        if(v[j]>key){ v[j+1]=v[j]; }
        else{ break; }
    }
    v[j+1]=key;
}

 

 

 

---

 

Radix Sort( 기수정렬 )

 

 

Radix Sort는 자주 쓰이지 않고 특수한 경우에만 쓰이는 정렬 방법이다. 낮은 자리수부터 비교하여 정렬하는 방법으로, 모든 원소가 정수일 때만 사용할 수 있다. 아래 예시를 보면서 이해하면 된다.

 

 

ex) {${128, 76, 54, 23, 234, 56}$}

 

  1) 1의 자리를 보고 정렬: {${23, 54, 234, 76, 56, 128}$}

  2) 10의 자리를 보고 정렬: {${23, 128, 234, 54, 56, 76}$}

  3) 100의 자리를 보고 정렬: {${23, 54, 56, 76, 128, 234}$}

 

 

시간복잡도가 $O(n·최대값의 자리)$으로 매우 빠르다는 특징이 있지만 모든 원소가 정수일 때만 사용할 수 있다.

 

 

int cnt=1; //최대 자릿수
queue<int> q[10]; //자리수 저장용
int mx=-999999999; //배열의 최댓값
for(int i=1; i<=n; i++){ mx=max(mx, v[i]); }
while(mx>0){
    cnt*=10;
    mx/=10;
}
for(int i=1; i<=cnt; i*=10){
    for(int j=1; j<=n; j++){
        int x=(v[j]/i)%(i*10);
        q[x].push(v[j]);
    }
    int idx=1;
    for(int j=0; j<10; j++){
        while(!q[j].empty()){
            v[idx++]=q[j].front();
            q[j].pop();
        }
    }
}
 

 

 

---

 

 

Counting Sort( 계수 정렬 )

 

 

 

Counting Sort는 각 데이터가 몇 개 존재하는지 세어 정렬하는 방법으로, 데이터의 범위가 크지 않다면 사용할 수 있는 매우 효율적인 정렬 방법이다. Counting Array를 활용하여 각 원소가 몇 개 존재하는지를 세고, 이후 Counting Array를 탐색하며 갯수만큼 그 원소를 반환한다.

 

ex) {0, 1, 4, 3, 5, 0, 2, 3, 4, 1, 3, 4}

     0: 2개  1: 2개  2: 1개  3: 3개  4: 3개  5: 1개

    따라서 0부터 5까지 각 숫자를 각 숫자의 개수만큼 출력하면 {0, 0, 1, 1, 2, 3, 3, 3, 4, 4, 4, 5}가 출력된다.

 

 

• 장점: 입력 받으면서 배열에 숫자의 개수를 기록할 수 있어 걸리는 시간이 매우 적다.
• 단점: 데이터의 범위가 주어져야만 사용할 수 있고 데이터의 범위가 크다면 사용하기 힘들다.

 

 

//데이터의 범위가 0~100000이라고 가정했을 때
int cnt[100001];
for(int i=1; i<=n; i++){
    cnt[ v[i] ]++;
}
int idx=1;
for(int i=0; i<=100000; i++){
    while(cnt[i]--){
        v[idx++]=i;
    }
}

 

 

---

 

 

 

지금까지 나온 정렬 방법은 시간복잡도가 $O(N^{2})$인 간단한 정렬이나, 원소들이 특정 조건을 만족할 때 사용할 수 있는 정렬 방법들을 소개했다. 이제는 $O(NlogN)$에 동작할 수 있는 정렬 알고리즘들에 대해 다룬다.

 

 

---

 

Merge Sort( 병합 정렬 )

 

 

Merge Sort는 분할 정복 알고리즘을 이용하는 정렬 방법으로, 데이터를 두 부분으로 분할하고, 그 분할된 데이터를 계속 분할하는 과정을 반복한 다음, 분할된 값들을 병합하면서 정렬하는 방법이다.

 

 

분할(Divide): 데이터를 두 부분으로 나눈다.

정복(Conquer): 두 부분 데이터를 병합한다.

 

 

 

위 그림에서 {7, 4, 2, 3} 부분을 먼저 살펴보자. {7, 4}는 {7}, {4}로 분할되고, 이들은 더 이상 분할될 수 없으므로 정복(Conquer)를 진행한다. {7}, {4}를 병합하는데, 더 작은 원소가 앞에 오도록 병합한다. 즉, Conquer의 결과가 {4, 7}이 된다.

마찬가지로 {2, 3} 또한 분할되어 {2}, {3}이 되고, 이들 또한 더 이상 분할될 수 없으므로 Conquer을 진행한다. {2}, {3}을 병합하면 {2, 3}이 된다.

이제 {4, 7}과 {2, 3}을 병합하는데 두 수열에서 가장 앞에 있는 원소들을 비교한다.

2 < 4이므로 Conquer의 결과는 {2, ...}로 시작하게 된다. 그 다음에는 {2, 3}에서 2의 다음인 3과 {4, 7}에서의 4를 비교한다.

3 < 4이므로 Conquer이 {2, 3, ...}이 된다. 이제 {2, 3}의 원소들이 모두 사용되었으므로 {4, 7}의 원소들을 Conquer의 결과에 그대로 삽입한다.

따라서 병합의 결과가 {2, 3, 4, 7}이다.

 

 

 

 

오른쪽의 Sub-Array 또한 {1, 5, 6, 8}을 이루게 되고 {2, 3, 4, 7}과 {1, 5, 6, 8}의 병합 과정을 살펴보면

 

1 < 2이므로 {1, ...}

5 > 2이므로 {1, 2, ...}

5 > 3이므로 {1, 2, 3, ...}

...

{1, 2, 3, 4, 5, 6, 7, 8}이 된다.

 

 

 

#include <iostream>
 
using namespace std;
 
int sorted[10];
 
//l~mid, mid+1~r의 두 수열을 병합
void Merge(int a[], int l, int mid, int r)
{
    int i=l, j=mid+1;
    int idx=l;
    while(i<=mid && j<=r){
        sorted[idx++]=(a[i]<a[j] ? a[i++] : a[j++]);
    }
    if(i<=mid){
        while(i<=mid){
            sorted[idx++]=a[i++];
        }
    }
    else{
        while(j<=r){
            sorted[idx++]=a[j++];
        }
    }
    for(int t=l; t<=r; t++){
        a[t]=sorted[t];
    }
}
 
//수열을 분할
void mergeSort(int a[], int l, int r)
{
    if(l==r){
        return;
    }
    int mid=(l+r)/2;
    mergeSort(a, l, mid);
    mergeSort(a, mid+1, r);
    Merge(a, l, mid, r);
}
 
int main()
{
    int arr[10];
    for(int i=0; i<10; i++){
        scanf("%d", &arr[i]);
    }
    mergeSort(arr, 0, 9);
    for(int i=0; i<10; i++){
        printf("%d ", arr[i]);
    }
    return 0;
}

 

 

이 때 수열을 병합하는 과정에서 모든 원소를 순차탐색하므로 $N$번의 반복 횟수가 존재하며, 수열을 분할하는 과정을 $logN$번 반복하므로(분할 트리의 높이가 $logN$) 시간복잡도는 $O(NlogN)$이다.

 

 

---

 

 

Quick Sort( 퀵 정렬 )

 

Quick Sort는 가장 유명한 정렬 알고리즘으로, 시간복잡도 $O(NlogN)$으로 동작한다. Pivot의 설정에 따라 $O(N^2)$으로 동작할 수 있는데, 이를 개선하기 위해 Pivot을 잡는 방법을 달리 하여 최악의 경우에도 $O(NlogN)$에 동작하게 할 수 있다. C/C++의 Algorithm 헤더 파일에 존재하는 sort 함수 또한 Quick Sort 기반으로 동작한다. 병합정렬처럼 분할정복으로 작동되는 정렬방법인데, 수열의 한 원소를 pivot으로 정하고 pivot의 값을 기준으로 pivot보다 작은 값은 pivot의 왼쪽, pivot보다 큰 값은 pivot의 오론쪽으로 옮기고 pivot의 위치를 기준으로 수열을 2개로 분할하여 위 과정을 반복한다.

 

 

 

먼저 수열의 가장 왼쪽을 pivot으로 정한다. 그리고 2번째 원소를 가리키고, $N$번째 원소를 가리키는 변수를 설정한다.

 

 

그 다음 왼쪽의 화살표가 가리키는 원소 중 pivot보다 큰 값이 나오면 화살표가 그곳을 가리키고, 오른쪽 화살표가 가리키는 원소 중 pivot보다 작은 값이 나오면 화살표가 가리켜서 두 값을 바꾸어준다.

 

 

위 과정을 실행하다가 두 화살표가 엇갈리게 되면 오른쪽 화살표 위치를 새로운 pivot으로 설정한다.

 

 

이렇게 수열이 두 부분으로 나누어졌고, 수열의 왼쪽은 pivot인 7보다 작은 원소들로만 구성되어 있고, 오른쪽은 pivot인 7보다 큰 원소들로만 구성이 되어있다. 이제 수열을 pivot을 기준으로 분할해서 위 과정을 계속 반복하면 수열이 정렬되게 된다.

 

 

 

//pivot을 정해주는 함수
int position(int *arr, int s, int e)
{
    int i=s, j=e;
    int pivot=arr[s];
    
    while(i<j){
        while(pivot<arr[j]){ j--; }
        while(i<j && arr[i]<=pivot){ i++; }
        swap(arr[i], arr[j]);
    }
    arr[s]=arr[j];
    arr[j]=pivot;
    return j;
}
 
void QuickSort(int *arr, int s, int e)
{
    if(s>=e){
        return;
    }
    int i=position(arr, s, e);
    //pivot을 기준으로 분할
    QuickSort(arr, s, i-1);
    QuickSort(arr, i+1, e);
}

 

 

퀵 정렬의 시간복잡도는 병합정렬과 마찬가지로 최선의 경우에는 $O(NlogN)$이지만, 최악의 경우에는 $O(N^{2})$이다. pivot을 단순히 맨 앞의 원소로 설정하는 것이 아니라 일정한 규칙을 두어 설정함으로서 시간복잡도를 개선할 수 있다. 또한 불필요한 데이터의 이동이 적은 장점 때문에 정렬 알고리즘 중에서는 거의 가장 효율적이라는 특징이 있다.