정렬(2) - 카운팅 정렬 / 퀵 정렬 / 병합 정렬

1. 계수 정렬 (Counting Sort)

※ 조건 : 입력값의 범위가 정해진 경우, 동시에 입력값의 최대값이 범위를 넘지 않는 경우에 사용 가능

'counting'이라는 단어를 해석하면 말 그대로 '수를 세는'이라는 뜻이 나온다. 

예시를 보면 쉽게 풀리는 문제이다. 하단의 표를 참고해보자. 

 

문제 : 5이하의 숫자까지 입력이 가능하며, 입력된 숫자들을 오름차 순으로 정렬하라.

입력값

3

3

3

2

1

2

4

5

5

해당 입력값을 1~5까지, 입력 된 숫자 크기로 정리를 해보면 하단과 같다. 

배열	1	2	3	4	5
갯수	1	2	3	1	2

이제 어떻게 하면 될까? 답은 간단하다. 

for문으로 배열의 값만큼 해당 수를 출력해주면 된다. 

 

관련 문제를 보고, 그에 대한 해답을 보면 군더더기 없이 정리가 된다. 

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

이 문제에서는 입력값이 최대 10,000라는 조건이 주어진다. 

#include <iostream>
using namespace std;

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;
    int arr[10001]={0,}; //배열의 갯수가 10001이라는 사실에 주의하자. 
    
    for(int i=0; i<T; i++){
        int a = 0;
        cin >> a;
        arr[a]++;
    }

    for(int i=1; i<10001; i++){ //배열의 최대값을 고려해서 10001이 주어지는 것을 주의하자. 
        if(arr[i]==0)
            continue;
        else if(arr[i]!=0)
            for(int j=0; j<arr[i]; j++)
                cout << i << "\n";
    }
    
    return 0;
}

 

 

---

 

2. 퀵 정렬 (Quick Sort)

이름 값 대로 빠르게 정렬하는 알고리즘.

선택 / 삽입 / 버블 정렬은 기본적으로 시간 복잡도가 O(N^2)이다. 

데이터가 십 만개가 넘어가면 일반적으로 활용하기는 애로사항이 존재한다. 

때문에 더 빠른 정렬의 알고리즘이 필요한데, '퀵정렬'이 빠른 정렬의 예시이다. 

퀵정렬은 대표적인 분할정복 알고리즘이며, 시간복잡도는 O(N*logN)이다. 

 

간단하게 아래 예시를 통해 설명될 수 있다. 

	<Pivot>	<bigger>			<smaller>
입력값	4	7	6	3	2	5

(1) 첫 번째 입력값이 Pivot이 된다.

(2) Pivot에서 오른쪽으로 큰 숫자를 찾고, 맨 마지막 입력값에서 부터 역방향으로 Pivot보다 작은 값을 찾는다. 

(3) 둘의 값을 바꿔준다. 서로 방향이 엇갈릴 때까지 계속한다. 

	<Pivot>	<changed>	<changed>	<changed>	<changed>
입력값	4	2	3	6	7	5

(4) 방향이 엇갈리면 Pivot과 작은 값에 해당 되는 수의 자리를 바꿔준다. 그리고 Pivot 값을 중심으로 양분한다. 

<Left>			<Pivot>	<Light>
입력값	3	2	4	6	7	5

(5) 1~3을 양 옆에서 반복진행 한다. 

 

이 과정이 반복진행되면 결국 정렬이 된다. 

#include <iostream>
#include <cmath>
using namespace std;

int number = 10;
int data[10] = {1,10,5,8,7,6,4,3,2,9};

void quickSort(int *data, int start, int end){
    if(start >= end){ //원소가 1개인 경우
        return;
    }
    
    int key = start; // 키(pivot)는 첫 번째 원소
    int i = start + 1; // 왼쪽부터 큰 값을 찾을 때 해당 인덱스를 의미
    int j = end; // 오른쪽부터 작은 값을 찾을 때 해당 인덱스를 의미
    int temp; // 두 값을 바꾸기 위한 임시 변수
    
    while (i<=j){ //엇갈리는 경우
        while(data[i]<= data[key]) // 키 값보다 큰 값을 만날때까지 오른쪽으로 이동
            i++;
        while(data[j] >= data[key] && j>start) // 키 값보다 작은 값을 만날때까지
            j--;
        if(i>j){ // 현재 엇갈린 상태면 키 값 교체
            temp = data[j];
            data[j] = data[key];
            data[key] = temp;
        } else { // 엇갈린건 아니지만 두 값을 바꿔줌 
            temp = data[j];
            data[j] = data[i];
            data[i] = temp;
        }
    }
    
    quickSort(data, start, j-1);
    quickSort(data, j+1, end);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    quickSort(data,0,number-1);
    for(int i=0; i<number; i++){
        cout << data[i] << "\n";
    }
    
    return 0;
}

 

왜 시간 복잡도가 빠른걸까?

만약 10개의 원소를 버블정렬로 진행한다 가정하자. 

일반적으로 버블정렬의 시간복잡도는 O(N^2), 즉, 100이다. 

퀵소트를 사용할 경우, 10개의 원소를 반씩 쪼개면 5개와 5개이고, 해당 원소들에 O(N^2)만 적용해도 25와 25가 나온다.

100보다는 훨씬 적은 값이 나오게 된다. 

 

하지만 최악의 경우, 시간복잡도가 O(N^2)인 사례가 있다. 

예를 들어 10가지의 원소가 있는 a[10] = {1,2,3,4,5,6,7,8,9,10}이 있다고 가정하자. 

이 경우 선택정렬과 별반 다를게 없는 정렬이 진행되므로, 시간복잡도는 O(N^2)에 해당된다. 

이 경우엔 차라리 삽입정렬이 더 빠르게 진행될 수 있다. 

 

---

 

3. 병합 정렬 (Merge Sort)

병합 정렬은 퀵 소트와 기본 구조는 흡사하다. 

'반씩 쪼개서' 정렬해본다 라는 개념과, 보통 시간 복잡도는 O(N*logN)이라는 점에서 퀵 소트와 큰 차이점이 없어보인다.

하지만 핵심적으로 Pivot값에 따라 편향 될 가능성이 있던 퀼 정렬과는 다르게, 

병합정렬은 항상 정확히 반씩 나누어서 최악의 경우에도 O(N*logN)을 보장한다는 차이점이 있다. 

 

#include <iostream>
#define number 8
using namespace std;

int sorted[8]; // 정렬 배열은 반드시 전역 변수로 선언

void merge(int a[], int m, int middle, int n){
    int i = m;
    int j = middle + 1;
    int k = m;
    // 작은 순서대로 배열에 삽입
    while (i<=middle && j <=n){
        if(a[i] <= a[j]){
            sorted[k] = a[i];
            i++;
        } else {
            sorted[k] = a[j];
            j++;
        }
        k++;
    }
    // 남은 데이터도 삽입
    if(i>middle) {
        for(int t=j; t<=n; t++){
            sorted[k] = a[t];
            k++;
          }
        }else{
            for(int t=i; t<=middle; t++){
                sorted[k] = a[t];
                k++;
            }
        }
    // 정렬된 배열을 삽입
        for(int t=m; t<=n; t++){
            a[t] = sorted[t];
        }
}

void mergeSort(int a[], int m, int n){
    // 이외의 경우는 크기가 1개인 경우
    if(m<n) {
        int middle = (m+n) / 2;
        mergeSort(a,m,middle);
        mergeSort(a,middle+1,n);
        merge(a,m,middle,n);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int array[number] = {7,6,5,8,3,5,9,1};
    mergeSort(array,0,number-1);
    for(int i=0; i<number; i++){
        cout << array[i] << " ";
    }
    
    return 0;
}

https://www.youtube.com/watch?v=QAyl79dCO_k&t=318s

불러오는 중입니다...