정렬 알고리즘은 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 정렬 등등이 있다. 이것 또한 나중에 정리해보도록 하겠다.




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

  1. whitesh2p 2016.06.24 20:12

    선택 정렬 설명에서는 각 v[i]당 한번씩만 값이 바뀌는 것 같은데 소스에서는 여러번 바뀝니다~

    • BraveDave 2016.09.17 18:23

      소스가 공식을 따르고 있는 겁니다.

  2. 지나가던이 2016.07.23 15:01

    삽입정렬에서 Swap이 아니라 v[j +1] = list[j]로 가능합니다.~
    while이 key 값보다 작은 수에서 끝나고 v[j + 1]인 바로 우측에 key을 넣어서
    대입연산으로 인한 중복값을 지웁니다.

    • HwaToo 2017.06.18 20:22 신고

      넵. 확실히 swap보단 대입연산이 조금 더 효율적이겠으나,
      다른 정렬코드와의 일관성 유지 및 기존 코드, 위키피디아 이미지와 비교하여 조금 더 직관적으로 보이게 하려고 swap으로 구현하였었습니다.
      해당 사항 피드백 감사합니다. :)

  3. 지나가는사람2 2016.09.27 14:50

    삽입,선택정렬 소스코드보고 바로 내렸습니다. 혼자서 짜신건진 모르겠는데 너무 비효율적이네요.
    일단 선택정렬은 설명은 맞았는데 소스코드는 완전 틀렸습니다. 소스코드 보시면 버블정렬이랑 과정이 똑같습니다.
    최소값을 먼저 찾은 다음 Swap을 하셔야죠. 만약 데이터가 n개라면 swap 횟수는 n-1번 해야 정상입니다.
    이러니까 이 다음글에 성능 평가에서 버블정렬이랑 선택정렬 성능이 완전 똑같이 나오죠.

    다음 삽입정렬은 중간 과정에 Swap으로 해도 정렬은 되지만, Swap 대신에 대입연산 1줄만 써넣어도 되는걸 굳이 Swap으로 하는 바람에 정렬 알고리즘이 굉장히 비효율적으로 동작하네요.

    • HwaToo 2017.06.18 20:02 신고

      안녕하세요. 취업후 신입 적응기간이라 블로그 관리에 소홀했네요.

      취업준비 직전에 정리용도로 급하게 작성한거라 실수가 많았던거같습니다.

      다시 블로그 관리하면서 말씀해주신 사항에 대해 수정하도록 하겠습니다.

      삽입정렬에 대해서는 위에 작성한 것과 같이 어느정도 의도된 사항이 있었습니다.

      늦었지만 피드백 감사드립니다.

  4. 후아암 2017.02.20 13:46

    틀린 부분이 많습니다..

  5. ㅇㅁㅇ 2017.05.20 15:06

    "퀵정렬이 합병정렬보다 20%이상 빠르다." 가 맞는거 아닌가요?

  6. a 2017.09.20 14:51

    버블정렬 j는 v.size() 까지 돌려야됨 -1 삭제

  7. a 2017.09.20 14:52

  8. hyunPrincess 2017.10.21 21:22

    많은 도움이 되었습니다 ㅎㅎ..다음엔 swift로도 구현부탁리겠습니다

  9. 창주애비 2017.12.20 16:57

    오랜만에 알고리즘 공부하는데 많은 도움이 되었습니다.
    고맙습니다.

  10. cola9k 2018.02.05 19:49

    퀵 정렬에서 궁금한게 있는데요. 매개변수 s를 들고오고나서 처음 pivot 위치를 지정 할때 s를 지정하셨는데 이렇게 되면 항상 pivot의 위치가 처음이 되는게 아닌가요? 예시에서 처럼 3번째 위치에서 pivot 어떻게 설정되는지 궁금합니다.

  11. 혀나블 2018.09.04 17:34 신고

    도움이 많이 되었습니다 감사합니다. 다음엔 감자분석에 대해서 포스팅해주세요

  12. 알고리강로리 2018.10.17 13:41

    화투님 항상 정말 잘 보면서 공부하고 있습니다! 설명을 제일 직관적으로 이해하기 쉽게 해 주세요. 그래서 말인데 혹시 heap sort도 해 주실 수 있으신 가요?

  13. nothing 2018.10.19 01:13

    잘못된 부분이 많습니다.
    위에서 많이 지적해주셨지만 추가로 공간복잡도도 잘못된 것 같습니다.
    글을 읽고 잘못 배우실 분들이 많을까 걱정이네요

    Space Complexity
    Insertion: O(1)
    Selection: O(1)
    Bubble: O(1)
    Quick:O(log N)
    Merge: O(N)

+ Recent posts