알고리즘 취준

정렬 알고리즘 2

퀵,병합 정렬에 대하여 알아보자

Posted by kyoungIn on March 25, 2019

정렬 알고리즘

< 병합 정렬(Merge sort) >

  • ‘존 폰 노이만(John von Neumann)’이라는 사람이 제안한 방법

  • 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬 에 속하며, 분할 정복 알고리즘의 하나 이다.

  • 분할 정복(divide and conquer) 방법

    • 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.

    • 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다.

  • 과정 설명

    • 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다.

    • 그렇지 않은 경우에는정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.

    • 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.

    • 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

로직<오름차순>

  1. 현재 배열을 반으로 쪼갠다. 배열의 시작위치와 종료위치를 더한 값에 2 나누어 기준점을 찾는다.
  2. 계속 쪼개서 배열의 크기가 0또는 1일때까지 반복한다.
  3. 두 배열 A,B를 비교한다. 각각의 인덱스를 i,j라고 가정했을때, i=A의 시작 인덱스, j=B의 시작인덱스
  4. A[i]와 B[j]를 비교 이 중 작은 값을 새로운 배열 C에 삽입한다.
  5. 그리고 그 작은 값을 가지고 있던 배열 의 인덱스를 +1 해준다.
  6. 즉, A[i]가 더 작았다면 다음 비교는 A[i+1] 과 B[j] 이다.
  7. 이 과정을 한 배열이 끝까지 도달할떄까지 반복한다.
  8. 그러면 나머지 배열의 남은 값들을 배열 C에 차례대로 넣어준다.
  9. C를 원래 배열에 저장한다.

병합정렬의 시간복잡도는 두 배열 A(n/2) B(n/2) 를 정렬하기때문에 O(n/2+n/2) -> O(n)이라고 할 수 있다. 분할과정은 lgN만큼 일어나는데, N크기의 배열을 분할하면 N/2 N/2로 2개 -> N/4 N/4 N/4 N/4 로 4개…,즉,분할 과정은 매번 반씩 감소하므로 lgN 만큼 반복해야 크기가 1인 배열로 분할 할 수 있다.

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

장점

  • 안정적인 정렬 방법
  • 데이터의 분포에 영향을 덜 받는다. 즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다.
  • 만약 레코드를 연결 리스트(Linked List)로 구성하면, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다.
    • 제자리 정렬(in-place sorting)로 구현할 수 있다.
    • 따라서 크기가 큰 레코드를 정렬할 경우에 연결 리스트를 사용한다면, 합병 정렬은 퀵 정렬을 포함한 다른 어떤 졍렬 방법보다 효율적이다.

단점

  • 만약 레코드를 배열(Array)로 구성하면, 임시 배열이 필요하다.
  • 제자리 정렬(in-place sorting)이 아니다.
  • 레크드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <iostream>
#include <vector>
using namespace std;
vector<int> v{21,10,12,20,25,13,15,22};
void Merge(int s,int e,int m){
    vector<int> temp(8);
    int i=s , j=m+1, idx=s;// idx:새로운 배열의 인덱스
    
    while(i<=m &&j <=e){
        if(v[i]<=v[j])
            temp[idx++]=v[i++];
        else
            temp[idx++]=v[j++];
    }
    if(i>m){
        for(int t=j;t<=e;t++)
            temp[idx++]=v[t];
    }
    else{
        for(int t=i;t<=m;t++)
            temp[idx++]=v[t];
    }
    
    for(int t=s;t<=e;t++)
        v[t]=temp[t];
}
void MergeSort(int s,int e){//start,end

    if(s>=e) return;
    
    int m = (s+e)/2;
    MergeSort(s,m);
    MergeSort(m+1,e);
    Merge(s,e,m);

}
int main(){
    MergeSort(0,7);
    for(int i=0;i<8;i++)
        cout << v[i] << ' ';
}

< 퀵 정렬(Quick sort) >

  • ‘찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)’가 개발한 정렬 알고리즘
  • 퀵 정렬은 불안정 정렬 에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬 에 속한다.
  • 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법
  • 합병 정렬(merge sort)과 달리 퀵 정렬은 리스트를 비균등하게 분할한다
  • 과정 설명
    • 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.
    • 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다. (왼쪽원소 < 피벗 < 오른쪽원소 )
    • 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
    • 분할된 부분 리스트에 대하여 순환 호출 을 이용하여 정렬을 반복한다.
    • 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.
    • 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.
    • 리스트의 크기가 0이나 1이 될 때까지 반복한다.

로직

  • 피벗으로 잡을 값을 정한다.(맨 앞, 맨 뒤, 중간값, 랜덤값 중 선택)
  • 배열의 맨 왼쪽원소를 left, 오른쪽원소를 right로 두고
  • right 원소를 피벗과 비교하며 피벗보다 클 경우 right-1하고 다시 탐색 ,피벗보다 작을 경우 탐색을 멈춘다.
  • left 원소를 피벗과 비교하며 피벗보다 작을 경우 left +1하고 다시 탐색, 피벗보다 클 경우 탐색을 멈춘다.
  • left 원소와 right 원소를 스왑해준다.
  • 위의 3,4,5과정을 left>right가 될때까지 반복해준다.
  • 위 과정이 끝나면 피벗과 left를 바꿔준다.
  • 다시 0~left-1 , left~끝까지로 나눠 정렬 시작.

각 배열의 정렬은 크기 N만큼 비교하고, 분할과정은 lgN만큼 진행하므로 시간복잡도는 O(lgN) 하지만 최악의 경우(모든 원소가 다 정렬 되어있는 경우) 에는 O(n^2)의 시간복잡도를 가지지만 거의 이런 경우는 없다.

장점

  • 속도가 빠르다.
  • 시간 복잡도가 O(nlog₂n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
  • 추가 메모리 공간을 필요로 하지 않는다.
  • 퀵 정렬은 O(log n)만큼의 메모리를 필요로 한다.

단점

  • 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.

  • 퀵 정렬의 불균형 분할을 방지하기 위하여 피벗을 선택할 때 더욱 리스트를 균등하게 분할할 수 있는 데이터를 선택한다.

    EX) 리스트 내의 몇 개의 데이터 중에서 크기순으로 중간 값(medium)을 피벗으로 선택한다

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

//3.퀵 정렬
#include <iostream>
#include <vector>
using namespace std;
vector<int> v{21,10,12,20,25,13,15,22};
void QuickSort(int s,int e){
    if(s>=e) return;
  
    int pivot=v[s];
    int left=s+1,right=e;
    while(left<=right){//엇갈릴때까지
        while(v[left]<pivot && left<=e)
            left++;
        while(v[right]>pivot && s+1<=right)
            right--;
        
        if(left>right){//엇갈림
           swap(v[s],v[right]);
        }
        else{
            swap(v[left],v[right]);
        }
    }//while 	
  
    QuickSort(s,right-1);
    QuickSort(right+1,e);
}
int main(){
    QuickSort(0,7);
    for(int i=0;i<8;i++)
        cout << v[i] << ' ';
}

참고

https://hsp1116.tistory.com/33

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

https://hongku.tistory.com/149

FEATURED TAGS
Algorithm BOJ Programmers 취준 SWEA C++ 알고리즘 DataBase nodeJS CS OS nodeJs
FRIENDS