정렬 알고리즘 (2)

- 개요

기본적인 비교 기반 정렬 알고리즘에 이어서, 향상된 성능을 갖는 합병 정렬, 퀵 정렬, 그리고 힙 정렬에 대해서 살펴본다. 또한 비교 기반의 정렬 알고리즘이 아닌 데이터의 분포 특성을 이용하는 정렬 알고리즘으로서 계수 정렬과 기수 정렬에 대해서 학습한다.

 

• 학습목표

• 합병 정렬과 퀵 정렬의 동작과 특징을 이해할 수 있다.

---

• 힙 정렬의 개념, 동작, 그리고 성능과 특징을 이해할 수 있다.

---

• 비교 기반 정렬 알고리즘의 하한의 개념을 이해할 수 있다.

---

• 계수 정렬과 기수 정렬의 개념, 동작, 성능 그리고 특징을 이해할 수 있다.

• 합병 정렬과 퀵 정렬
  • 합병 정렬
    • 최선, 최악, 평균 수행 시간이 모두 O(nlogn)
    • 안정적인 정렬 알고리즘
    • 제자리 정렬 알고리즘이 아님
      • 데이터가 늘어나면 늘어날 수록 추가적인 저장 공간 m이 필요함
    • 비교기반 알고리즘중 유이할게 제자리 정렬 알고리즘이 아닌 알고리즘은 합병 정렬
  • 퀵 정렬
    • 최악 수행 시간 O(n^2), 최선/평균 수행 시간 O(nlogn)
      • 피벗 선택의 임의성만 보장되면 평균적인 성능을 보일 가능성이 매우 높음
    • 안정적이지 않은 정렬 알고리즘
      • 상대적인 순서가 유지되지 않음
    • 제자리 정렬 알고리즘
    •  
  • 힙정렬
    • 힙자료구조의 장점을 활용한 정렬 방식
      
      • 임의의 값 삽입과 최댓값 삭제가 용이
  • (최대) 힙heap?
    • 완전 이진 트리
    • 각 노드의 값은 자신의 자식 노드의 값보다 크거나 같다.
    • 1차원 배열로 변환하면 용이
  • 힙의 장점
    • 임의의 값의 삽입 용이
    • 최댓값 삭제 과정
      • 마지막 노드와 제일 위 노드랑 변경
      • 마지막 노드의 위치를 둘 중에 더 큰 값과 변경
      • 반본적으로 변경에서 힙 재구성 (부모 노드 >= 자식 노드 이도록)
  • 힙 정렬의 처리 과정
    • 1단계 - 1차원 배열 -> 힙으로 변환
    • 2단계 - 힙 재구성 [ 반복 ( 힙의 최댓값 삭제, 힙의 재구성 ) ]
  • 초기 힙 구축
    • 1차원 입력 배열 -> 힙
    • 두가지 접근 방법
      • 1) 주어진 입력 배열의 각 원소에 대한 힙에서의 삽입 과정을 반복
      • 2) 주어진 입력 배열을 우선 완전 이진 트리로 만든 다음에 아래에서 위로 그리고 오른쪽에서 왼쪽으로 진행하면서 각 노드에 대해서 힙의 조건을 만족할 수 있도록 조정
        • 자식이 없는 노드 : 리프 노드는 그대로 힙, 위로 진행, 오른쪽에서 왼쪽으로 진행해서 힙 구축
    • 성능 분석
      • 최선, 최악, 편균의 경우 모두 O(nlogn)
        • 초기 힙 생성, 최댓값 삭제 및 힙 재구성
          • 바깥 루프 -> 입력 크기 n에 비례
          • 안쪽 루프 -> 완전 이진 트리의 높이 logn에 비례
    • 안정적이지 않은 정렬 알고리즘
    • 제자리 정렬 알고리즘
• 비교 기반 정렬 알고리즘
  • 키값과 키값을 직접적으로 비교해서 크고 작음에 따라 순서를 정하는 방식
    • 기본 성능 O(n^2)인 알고리즘 -> 버블, 선택, 삽입, 셀
    • 향상된 성능 O(nlong)인 알고리즘 -> 합병, 퀵, 힙
  • 비교 기반으로서 O(nlogn)보다 더 효율적인 성능의 정렬 알고리즘을 개발할 수 있는가?
    • 비교 기반 정렬 알고리즘의 하한이 O(nlogn) 인가?
  • 특징
    • n=3인 세 개의 다른 숫자 a,b,c를 정렬하는 결정 트리
    • n개의 서로 다른 값을 정렬
      • 정확히 n!개의 리프 노드를 갖는 결정 트리
    • n개의 서로 다른 값을 정렬하는 데 필요한 키의 비교 횟수
      • n!개의 리프 노드를 가진 결정 트리의 높이
      • m개의 리프 노드를 가진 이진 트리의 높이 h >= [logm]
      • n개의 서로 다른 값을 정렬하는 비교 기반 알고리즘의 최소의 비교 횟수 [log(n!)]
      • log(n!) >= nlogn -1.45n
      • 비교 기반 정렬 알고리즘의 하한 O(nlogn)

 

▷ 퀵 정렬 → 최악의 시간 복잡도 O(n2), 평균적인 경우 O(nlogn), 안정적이지 않은 정렬, 제자리 정렬

▷ 합병 정렬 → 최악/평균의 시간 복잡도 O(nlogn), 안정적 정렬, 제자리 정렬이 아님

 

분포 기반 정렬

• 계수 정렬
  • 비교 기반이 아닌 데이터의 분포를 이용한 정렬
    • 계수 정렬, 기수 정렬 -> 선형 시간 O(n)
  • 주어진 원소 중에서 자신보다 작거나 같은 값을 갖는 원소의 개수를 계산하여 counting 정렬할 위치를 찾아 정렬하는 방식
    • 입력값이 어떤 작은 정수 범위 내에 있다는 것을 알고 있는 경우에만 적용
      • 입력값의 범위 a-b에 해당하는 크기의 배열... 입력값의 출현 횟수의 누적값 계산, 
      • 성능 분석
        • O(n+k ) ->입력값의 범위 K가 입력 크기 n에 비례한다면 O(n
    • 특징
      • 입력값의 범위가 입력 원소의 개수보다 작거나 비례할 때 유용
      • 안정적인 정렬 알고리즘
      • 제자리 정렬 알고리즘이 아님
      • 보편적이지 못한 방법
        • 입력값의 범위를 알아야 함
        • 추가적인 배열이 필요함 COUNT[],B[]
• 기수 정렬
  • 입력값을 자릿수별로 부분적으로 비교하는 정렬 방식
    • 주어진 원소의 키값을 자릿수별로 나누고, 각 자릿수별로 계수 정렬과 같은 안정적인 정렬 알고리즘을 반복적으로 적용하여 정렬
    • LSD (Least Significant Digit) 기수 정렬 -> 낮은 자리부터 높은 자리로 진행
    • MSD (Most Sig~ Digit) 기수 정렬 -> 높은 자리부터 낮은 자리로 진행
  • 성능 분석
    • 각 원소의 i자리의 값에 대해서 안정적인 정렬 알고리즘 적용
    • 계수 정렬을 사용하면 O(dn) -> d[자릿수]가 입력 크기 n보다 매우 작으면 O(n)
    • 입력 원소의 값의 자릿수가 상수일 때 유용
    • 안정적인 정렬 알고리즘
    • 제자리 정렬 알고리즘이아님
      • 계수 정렬 -> 전체 데이터 개수와 진법 크기만큼의 추가적인 공간이 필요
• 기수 정렬은 주어진 원소들의 키값을 자릿수별로 나누고, 각 자릿수별(예를 들어 낮은 자리부터 높은 자리)로 반복해서 계수 정렬과 같은 안정적 알고리즘을 적용하여 정렬하는 방법이다. 따라서 정렬 과정에서 내부적으로는 안정적인 정렬 알고리즘을 사용해야 한다.
• 비교 기반 정렬 알고리즘(버블 정렬, 선택 정렬, 삽입 정렬, 셸 정렬, 합병 정렬, 퀵 정렬, 힙 정렬) 중에서 합병 정렬만 제자리 정렬 알고리즘이 아니다. 합병 정렬에서는 부분배열의 정렬 결과를 저장하기 위한 추가적인 공간 O(n)이 요구된다. 한편 데이터 분포 기반 정렬 알고리즘(계수 정렬, 기수 정렬)은 모두 제자리 정렬 알고리즘이 아니다.
• 알고리즘 정리
•  
•