[algorithm] 합병정렬, 퀵정렬, 힙정렬, 계수, 기수 정렬

• 합병 정렬과 퀵 정렬
  • 주어진 배열을 동일한 크기의 두부분 배열로 분할
  • 정렬된 두 부분 배열을 합쳐서 하나의 정렬된 배열을 만듦
  • 합병 정렬의 성능과 특징
    • 최선/최악/평균 수행 시간이 모두 O(nlogn)
    • 안정적인 정렬 알고리즘
• 퀵 정렬
  • 퀵정렬의 성능과 특징
    • 최악 수행 시간 O(n^2), 최선/평균 수행 시간 O(nlogn)
      • 피벗 선택의 임의성만 보장되면 평균 성능을 보일 가능성이 매우 높음
    • 제자리 정렬 알고리즘
    • 안정적이지 않은 정렬 알고리즘
• 힙 정렬
  • 힙 자료구조의 장점을 활용한 정렬
  • (최대)힙
    • 완전 이진 트리
    • 각 노드의 값은 자신의 자식 노드의 값보다 크거나 같다.
  • 힙의 장점
    • 임의의 값 삽입과 최대값 삭제가 용이
  • 힙의 구현
    • 일차원 배열
      • 부모노드: i
      • 자식노드: 2i+1(왼쪽 노드), 2i+2(오른쪽 노드)
      • 자식노드(j)에서 부모노드를 찾아가고자 한다면 (j-1)/2
  • 임의의 값의 삽입
    • 최대값 삭제
    • 힙 정렬의 처리 과정
      • 1차원 배열 -> 힙으로 변환
      • 데이터의 개수만큼 아래과정을 반복함
        • 힙의 최대값 삭제
        • 힙의 재구성

HeapSort(A[], n){
    for(i=0; i<n; i++){
        par = (i/2) - 1;
        while(par >= 0 && A[par] < A[i]){
            A[par]과 A[i]의 교환;
            i = par;
            par = (i/2) - 1;
        }
    }
    for(i=n-1; i>0; i--){
        최대값 A[0]과 마지막노드 A[i]의 교환;
        cur = 0; lch = 1; rch = 2;
        do{
            if(rch < i && A[lch] < A[rch]) lch = rch;
            if(A[lch] > A[cur]) {
                A[cur]과 A[lch]의 교환;
                cur = lch;
                lch = cur*2 + 1;
                rch = cur*2 + 2;
            }
            else lch = i;
        } while( lch < i)
    }
}

•  
  •  
    • 초기 힙 구축
      • 1차원 입력 배열 --변환--> 힙
      • 두 가지 방법
        • 방법1 -> 주어진 입력 배열의 각 원소에 대해 힙에서의 삽입 과정을 반복
        • 방법2 -> 주어진 입력 배열을 우선 완전 이진 트리로 만든 다음에 아래에서 위로, 오른쪽에서 왼쪽으로 진행하면서 각 노드에 대해 힙의 조건이 만족되도록 자손 노드의 값과의 비교, 교환을 통해 조정
    • 힙 정렬의 두 번째 단계(최대값 삭제 -> 힙 재구성)
    • 성능 분석
      • 최선, 최악, 평균의 경우 -> O(nlogn)
        • 초기 힙 생성, 최대값 삭제 및 힙 재구성
          • 바깦 루프 -> 입력 크기. n에 비례
          • 안쪽 루프 -> 완전 이진 트리의 높이 logn에 비례
    • 특징
      • 안정적이지 않은 정렬 알고리즘
      • 제자리 정렬 알고리즘
• 비교 기반 정렬 알고리즘
  • 키값을 직접적으로 비교해서 크기에 따라 순서를 정하는 방식
    • 기본 성능 O(n^2) -> 버블 정렬, 선택 정렬, 삽입 정렬, 셸 정렬
    • 향상된 성능 O(nlogn) -> 합병 정렬, 퀵 정렬, 힙 정렬
  • 비교 기반으로 O(nlogn)보다 더 효율적인 성능의 정렬 알고리즘은 존재하는가?
    • 비교 기반 정렬 알고리즘의 하한이 O(nlogn)인가?
      • 하한 lower bound -> 최소한으로 필요한 성능, 가장 좋은 성능
  • 비교 기반 정렬 알고리즘의 하한은?
    • n=3인 세 개의 다른 숫자 a,b,c를 정렬하는 결정 트리
      •  비교 기반 정렬 알고리즘의 하한 O(nlogn)
• 계수 정렬
  • 비교 기반이 아닌 데이터의 분포를 이용한 정렬 방식
    • 계수counting 정렬, 기수radix 정렬 -> 선형 시간 O(n)
  • 주어진 원소 중에서 자신보다 작거나 같은 값을 갖는 원소의 개수를 계산하여 counting 정렬할 위치를 찾아 정렬하는 방식
    • 입력값이 어떤 작은 정수 범위 내에 있다는 것을 알고 있는 경우에만 적용 가능
      • 입력값의 범위 a~b에 해당하는 크기의 배열 COUNT[a,b]를 할당하고, 각 입력값을 한 번 조사하여 각 입력값의 출현 횟수의 누적값을 계산하여 적용
  • 특징
    • 입력값의 범위가 입력 원소의 개수보다 작거나 비례할 때 유용
      • 입력값의 범위를 k라고 할 때 O(n+k)시간
        • 보통 k=O(n)일 때, 사용하므로 결국 선형 시간 O(n)을 가짐
    • 안정적인 정렬 알고리즘
    • 제자리 정렬 알고리즘이 아님
    • 보편적이지 못한 방법
      • 입력값의 범위를 미리 알아야 함
      • 추가적인 배열이 필요 -> COUNT[], B[]
• 기수 정렬
  • 입력값을 자릿수별로 부분적으로 비교하는 정렬
    • 주어진 데이터의 키값을 자릿수별로 나누고, 각 자릿수별로 계수 정렬과 같은 안정적인 정렬 알고리즘을 반복적으로 적용하여 정렬하는 방식
      • LSD(Least Significant Digit) 기수 정렬 -> 낮은 자리부터 높은 자리로 진행
      • MSD(Most Significant Digit) 기수 정렬 -> 높은 자리부터 낮은 자리로 진행
  • 성능 분석
    • O(dn)
      • d가 입력 크기 n보다 매우 작으면 O(n)
  • 특징
    • 입력 원소의 값의 자릿수가 상수일 때 유용
      • d 자릿수 n개의 숫자들에 대해 계수 정렬을 적용하면 O(dn)
        • 여기서 d를 상수로 간주하면 O(n)
    • 안정적인 정렬 알고리즘
    • 제자리 정렬 알고리즘이 아님
      • 계수 정렬 -> 전체 데이터 개수와 진법 크기만큼의 추가 공간이 필요