정렬 알고리즘은 n개의 숫자가 입력으로 주어졌을 때, 이를 사용자가 지정한 기준에 맞게 정렬하여 출력하는 알고리즘이다.

예를 들어 n개의 숫자가 저장되어있는 배열을, 오름차순의 조건으로 작성하여 입력하면 오름차순으로 정렬된 배열을 출력으로 구할 수 있다.

정렬 알고리즘은 정말 다양한데, 이에 따라 각각의 수행시간도 천차 만별이다.

여기서는 우선 O(N^2), O(NlgN)인 알고리즘을 보려고 한다.


1. 선택 정렬(Selection Sort)


선택 정렬은 이름에 맞게 현재 위치에 들어갈 값을 찾아 정렬하는 배열이다. 현재 위치에 저장 될 값의 크기가 작냐, 크냐에 따라 최소 선택 정렬(Min-Selection Sort)와 최대 선택 정렬(Max-Selection Sort)로 구분 할 수 있다.

최소 선택 정렬은 오름차순으로 정렬될 것이고, 최대 선택 정렬은 내림차순으로 정렬될 것이다.


기본 로직은 다음과 같다.

① 정렬 되지 않은 인덱스의 맨 앞에서 부터, 이를 포함한 그 이후의 배열값 중 가장 작은 값을 찾아간다.

(정렬되지 않은 인덱스의 맨 앞은, 초기 입력에서는 배열의 시작위치일 것이다.)

② 가장 작은 값을 찾으면, 그 값을 현재 인덱스의 값과 바꿔준다.

③ 다음 인덱스에서 위 과정을 반복해준다.


이 정렬 알고리즘은 n-1개,n-2개,..,1개씩 비교를 반복한다.

배열이 어떻게 되어있던지간에 전체 비교를 진행하므로 시간복잡도는 O(n^2)이다.


공간복잡도는 단 하나의 배열에서만 진행하므로 O(n)이다.



<선택 정렬>


선택 정렬 C++ 소스코드


(이전에는 temporary 변수에 해당 키 값을 저장하지 않고 그냥 그때그때 스왑하도록 하였으나.

다른 분들의 피드백으로 수정하였습니다)

void selectionSort(vector<int> v){
    for(int i=0;i<v.size()-1;i++){
        int tmp = i;
        for(int j=i+1;j<v.size();j++){
            if(v[tmp]>=v[j]) tmp = j;
        }
        swap(v[i], v[tmp]);
    }
}



2. 삽입 정렬(Insertion Sort)


삽입 정렬은 현재 위치에서, 그 이하의 배열들을 비교하여 자신이 들어갈 위치를 찾아, 그 위치에 삽입하는 배열 알고리즘이다.


기본 로직은 다음과 같다.

① 삽입 정렬은 두 번째 인덱스부터 시작한다. 현재 인덱스는 별도의 변수에 저장해주고, 비교 인덱스를 현재 인덱스 -1로 잡는다.

② 별도로 저장해 둔 삽입을 위한 변수와, 비교 인덱스의 배열 값을 비교한다. 

③ 삽입 변수의 값이 더 작으면 현재 인덱스로 비교 인덱스의 값을 저장해주고, 비교 인덱스를 -1하여 비교를 반복한다.

④ 만약 삽입 변수가 더 크면, 비교 인덱스+1에 삽입 변수를 저장한다.


이 정렬 알고리즘 또한 최악의 경우(역으로 정렬되어있을 경우)엔 n-1개,n-2개,..,1개씩 비교를 반복하여 시간복잡도는 O(n^2)이지만.

이미 정렬되어 있는 경우에는 한번씩 밖에 비교를 하지 않아 시간 복잡도는 O(n)이다.
하지만 상한을 기준으로 하는 Big-O notation은 최악의 경우를 기준으로 평가하므로 삽입 정렬의 시간복잡도는 O(n^2)이다.

공간복잡도는 단 하나의 배열에서만 진행하므로 O(n)이다.


<삽입 정렬>

삽입 정렬 C++ 소스코드

//삽입 정렬
void insertionSort(vector<int> v){
    for(int i=1;i<v.size();i++){
        int key = v[i], j = i-1;
            while(j>=0 && key <v[j]){
                swap(v[j], v[j+1]);
                j--;
            }
            v[j+1] = key;
        }   
}


위 코드는 위키피디아 이미지를 통해 좀 더 이해를 쉽게하고자 swap 함수를 이용하였으나, 사실 swap이 아닌 대입연산을 사용하는 것이 조금 더 적합하다.

swap(v[j], v[j+1]) => v[j+1] = v[j]


3. 버블 정렬(Bubble Sort)


버블 정렬은 매번 연속된 두개 인덱스를 비교하여, 정한 기준의 값을 뒤로 넘겨 정렬하는 방법이다. 

오름차순으로 정렬하고자 할 경우, 비교시마다 큰 값이 뒤로 이동하여, 1바퀴 돌 시 가장 큰 값이 맨 뒤에 저장된다.

맨 마지막에는 비교하는 수들 중 가장 큰 값이 저장 되기 때문에, (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼만 반복해 주면 된다.


기본 로직은 다음과 같다.

① 삽입 정렬은 두 번째 인덱스부터 시작한다. 현재 인덱스 값과, 바로 이전의 인덱스 값을 비교한다.

② 만약 이전 인덱스가 더 크면, 현재 인덱스와 바꿔준다. 

③ 현재 인덱스가 더 크면, 교환하지 않고 다음 두 연속된 배열값을 비교한다.

④ 이를 (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼 반복한다.


이 정렬 알고리즘은 1부터 비교를 시작하여, n-1개,n-2개,..,1개씩 비교를 반복하며,

선택 정렬과 같이 배열이 어떻게 되어있던지간에 전체 비교를 진행하므로 시간복잡도는 O(n^2)이다.

공간복잡도도 이 또한 단 하나의 배열에서만 진행하므로 O(n)이다.


<버블 정렬>


버블 정렬 C++ 소스코드

//버블 정렬 
void bubbleSort(vector<int> v){
    for(int i=0;i<v.size()-1;i++){
        for(int j=1; j<v.size()-i;j++)
            if(v[j-1] > v[j])
                swap(v[j-1],v[j]);
        
    }
}




4. 합병 정렬(Merge Sort)


합병 정렬은 분할 정복(Divide and conquer) 방식으로 설계된 알고리즘이다. 분할 정복은 큰 문제를 반으로 쪼개 문제를 해결해 나가는 방식으로,

분할은 배열의 크기가 1보다 작거나 같을 때 까지 반복한다.


입력으로 하나의 배열을 받고, 연산 중에 두개의 배열로 계속 쪼게 나간 뒤, 합치면서 정렬해 최후에는 하나의 정렬을 출력한다.


합병은 두 개의 배열을 비교하여, 기준에 맞는 값을 다른 배열에 저장해 나간다.

오름차순의 경우 배열 A,배열 B를 비교하여 A에 있는 값이 더 작다면 새 배열에 저장해주고, A인덱스를 증가시킨 후 A,B의 반복을 진행한다.

이는 A나 B중 하나가 모든 배열값들을 새 배열에 저장할 때 까지 반복하며, 전부 다 저장하지 못한 배열의 값들은 모두 새 배열의 값에 저장해준다.


분할 과정의 기본 로직은 다음과 같다.

① 현재 배열을 반으로 쪼깬다. 배열의 시작 위치와, 종료 위치를 입력받아 둘을 더한 후 2를 나눠 그 위치를 기준으로 나눈다.

② 이를 쪼갠 배열의 크기가 0이거나 1일때 까지 반복한다.


합병 과정의 기본 로직은 다음과 같다.

① 두 배열 A,B의 크기를 비교한다. 각각의 배열의 현재 인덱스를 i,j로 가정하자.

② i에는 A배열의 시작 인덱스를 저장하고, j에는 B배열의 시작 주소를 저장한다.

③ A[i]와 B[j]를 비교한다. 오름차순의 경우 이중에 작은 값을 새 배열 C에 저장한다. 

    A[i]가 더 컸다면 A[i]의 값을 배열 C에 저장해주고, i의 값을 하나 증가시켜준다.

④ 이를 i나 j 둘중 하나가 각자 배열의 끝에 도달할 때 까지 반복한다.

⑤ 끝까지 저장을 못한 배열의 값을, 순서대로 전부 다 C에 저장한다.

⑥ C 배열을 원래의 배열에 저장해준다.


이 정렬 알고리즘은 분할 과정과 합병 과정이 나뉘어진다.


합병 과정은 두 배열 A,B를 정렬하기 때문에, A배열의 크기를 N1, B배열의 크기를 N2라고 할 경우

O(n1+n2)와 같다. 배열 A와 배열 B는 하나의 배열을 나눈 배열들이기 때문에 전체 배열의 길이가 N이라고 할 경우

N = N1 + N2이므로 O(N)이라고 할 수 있다.


분할 과정은 lgN만큼 일어나는데, 이 이유는 간단하다. 크기가 N인 배열을 분할하면, 한번 분할하면 N/2,N/2 2개, 그다음 분할하면 N/4,N/4,N/4,N/4 4개.

즉 분할 과정은 매번 반씩 감소하므로 lgN만큼 반복해야 크기가 1인 배열로 분할 할 수 있다.


각 분할별로 합병을 진행하므로, 합병정렬의 시간 복잡도는 O(NlgN) 이다.

사용하는 공간은 정렬을 위한 배열을 하나 더 생성하므로 2N개 사용한다. 


<합병 정렬>

합병 정렬 C++ 소스코드

//합병 void merge(vector<int>& v, int s, int e, int m) { vector<int> ret; int i = s, j = m + 1, copy = 0; //결과를 저장할 배열에 하나씩 비교하여 저장한다. while (i <= m && j <= e) { if (v[i] < v[j])ret.push_back(v[i++]); else if (v[i] > v[j])ret.push_back(v[j++]); } //남은 값들을 뒤에 채워넣어준다. while (i <= m) ret.push_back(v[i++]); while (j <= e) ret.push_back(v[j++]); //원래 배열에 복사해준다. for (int k = s; k <= e; k++) { v[k] = ret[copy++]; } } //합병 정렬 void mergeSort(vector<int>& v, int s, int e){ if(s<e){ int m = (s+e)/2; /*divide, 분할*/ mergeSort(v,s,m); //s부터 m까지 mergeSort(v,m+1,e); //m+1부터 e까지 /*conquer, 합병*/ merge(v,s,e,m); } }




5. 퀵 정렬(Quick Sort)


퀵 정렬 또한 분할 정복(Divide and conquer)을 이용하여 정렬을 수행하는 알고리즘이다. 

pivot point라고 기준이 되는 값을 하나 설정 하는데, 이 값을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 옮기는 방식으로 정렬을 진행한다.

이를 반복하여 분할된 배열의 크기가 1이되면 배열이 모두 정렬 된 것이다.


기본 로직은 다음과 같다.

① pivot point로 잡을 배열의 값 하나를 정한다. 보통 맨 앞이나 맨 뒤, 혹은 전체 배열 값 중 중간값이나나 랜덤 값으로 정한다.

② 분할을 진행하기에 앞서, 비교를 진행하기 위해 가장 왼쪽 배열의 인덱스를 저장하는 left 변수, 가장 오른쪽 배열의 인덱스를 저장한 right변수를 생성한다. 

③ right부터 비교를 진행한다. 비교는 right가 left보다 클 때만 반복하며. 비교한 배열값이 pivot point보다 크면 right를 하나 감소시키고 비교를 반복한다.

    pivot point보다 작은 배열 값을 찾으면, 반복을 중지한다.

④ 그 다음 left부터 비교를 진행한다. 비교는 right가 left보다 클 때만 반복하며. 비교한 배열값이 pivot point보다 작으면 left를 하나 증가시키고 비교를 반복한다.

    pivot point보다 큰 배열 값을 찾으면, 반복을 중지한다.

⑤ left 인덱스의 값과 right 인덱스의 값을 바꿔준다.

⑥ 3,4,5 과정을 left<right가 만족 할 때 까지 반복한다.

⑦ 위 과정이 끝나면 left의 값과 pivot point를 바꿔준다.

⑧ 맨 왼쪽부터 left - 1까지, left+1부터 맨 오른쪽까지로 나눠 퀵 정렬을 반복한다.


퀵 정렬은 분할과 동시에 정렬을 진행하는 알고리즘이다.

각 정렬은 배열의 크기 N만큼 비교하며, 이를 총 분할 깊이인 lgN만큼 진행하므로 총 비교횟수는 NlgN, 즉 시간 복잡도는 O(NlgN)이다.

다만 퀵 정렬에는 최악의 경우가 존재하는데, 이는 배열이 이미 정렬이 되어있는 경우이다. 이 경우 분할이 N만큼 일어나므로 시간 복잡도는 O(N^2)이다.

이를 방지 하기 위해 앞서 언급했던 전체 배열 값 중 중간값이나나 랜덤 값으로 pivot point를 정하는 방법을 쓰기도 한다.


최악의 경우 때문에 합병 정렬보다 느린 알고리즘이라 생각하기 쉽지만, 발생하기 쉽지 않은 경우이고, 일반적으로 퀵 정렬이 합병정렬보다 20%이상 빠르다고 한다.

이는 바로 다음에 포스트할 정렬의 성능 측정 부분에서 보도록 하겠다.


<퀵 정렬>


퀵 정렬 C++ 소스코드

//퀵 정렬 
void qsort(vector<int>& v, int s, int e) {
    int pivot = v[s];
    int bs = s, be = e;
    while (s<e) {   
        while (pivot <= v[e]&&s<e) e--;
        if (s>e) break;
        while (pivot >= v[s]&&s<e) s++;
        if (s>e) break;
        std::swap(v[s], v[e]);
    }
    std::swap(v[bs], v[s]);
    if(bs<s)
        qsort(v,bs, s-1);
    if(be>e)
        qsort(v,s+1, be);

}



그 외 똑같이 NlgN에 작동하는 힙 정렬, 선형 시간에 작동하는 Count 정렬, Radix 정렬 등등이 있다. 이것 또한 나중에 정리해보도록 하겠다.




<이미지 출처 : 위키피디아>

+ Recent posts