(─━┘_└━─)/ 머리만1톤(Head1Ton)

계수 정렬(Counting Sort)

• 특수 정렬 알고리즘(기수 정렬, 계수 정렬) 중 하나.
  
  
• 계수 정렬의 개념
• 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하면서 선형 시간에 정렬하는 효율적인 알고리즘
  
  
• 속도가 빠르며 안정적이다.
  
  
• 제한 사항
• 정수나 정수로 표현할 수 있는 자료에 대해서만 동작
• 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 한다.

• 계수 정렬 수행 과정

• 1단계
  1. Data에서 각 항목들의 발생 횟수를 센다.
  2. 횟수들은 정수 항목들로 직접 인덱스 되는 카운트 배열 Counts에 저장

• 1단계
  3. 정렬된 집합에서 각 항목의 앞에 위치할 항목의 개수를 반영하기 위하여 카운트들을 조정한다.

• 2단계 : 정렬된 집합
  1. Temp에 1을 삽입하고 Counts[1]을 감소시킨 후

• 2단계 : 정렬된 집합
  2. Temp에 4을 삽입하고 Counts[4]을 감소시킨 후

• 2단계 : 정렬된 집합
  3. Temp에 2을 삽입하고 Counts[2]을 감소시킨 후

• 2단계 : 정렬된 집합
  4. Temp에 1을 삽입하고 Counts[1]을 감소시킨 후

• 2단계 : 정렬된 집합
  5. Temp에 3을 삽입하고 Counts[3]을 감소시킨 후

• 2단계 : 정렬된 집합
  6. Temp에 0을 삽입하고 Counts[0]을 감소시킨 후

기수 정렬(Radix Sort)

• 특수 정렬 알고리즘(기수 정렬, 계수 정렬) 중 하나.
  
  
• 특수 정렬 알고리즘
• 비교 정렬
• 두 원소를 비교하는 정렬의 하한선은 Ω(nlogn)
  
  " 최악의 경우 정렬 시간이 θ(nlogn)보다 더 빠를 수는 없는가? "
  
  
• 그러나 원소들이 특수한 성질을 만족하면 O(n)정렬도 가능하다.
• 기수 정렬
  - 원소들이 모두 k 이하의 자리 수를 가졌을 때 (k: 상수)
  
  
• 기수 정렬의 개념
• 입력이 모두 K 이하의 자리 수를 가진 특수한 경우에(자연수가 아닌 제한된 종류를 가진 알파벳 등도 해당) 사용할 수 있는 방법
  
  
  
• θ(n)시간이 소요되는 알고리즘
  
  
• 기수 정렬 수행 과정 #1
• 원소들의 일의 자리부터 비교 후 정렬, 다음은 십의 자리를 비교 후 정렬 ...

• 기수 정렬의 수행 과정 #2
• 정렬되지 않은[69, 10, 30, 2, 16, 8, 31, 22]의 자료들을 기수 정렬 방법으로 정렬하는 과정을 살펴보자.
• 키 값이 두 자리 십진수 이므로, 10개의 버킷을 사용하여 기수 정렬을 두 번 반복한다.

1. 초기 상태 : 큐(여러 개의 원소들이 일정한 순서로 나열된 자료 구조이며, 스택과는 달리 한쪽 끝에서는 삽입만 할 수 있고, 삭제는 반대쪽 끝에서만 할 수 있도록 되어 있음)를 사용하여 0부터 9까지 10개의 버킷을 만든다.

2. 키 값의 일의 자리에 대해서 기수 정렬 수행 [1단계]

- 정렬할 원소의 일의 자리 값에 따라서 순서대로 버킷에 분배 -

2. 키 값의 일의 자리에 대해서 기수 정렬 수행 [2단계]

- 버킷에 분배된 원소들을 순서대로 꺼내서 저장 -

3. 키 값의 십의 자리에 대해서 기수 정렬 수행 [1단계]

 - 정렬할 원소의 십의 자리 값에 따라서 순서대로 버킷에 분배 -

3. 키 값의 십의 자리에 대해서 기수 정렬 수행 [2단계]

 - 버킷에 분배된 원소들을 순서대로 꺼내서 저장 -

• 기수 정렬 알고리즘 분석
• 메모리 사용공간
• 원소 n개에 대해서 n개의 메모리 공간 사용
• 기수 r 에 따라 버킷 공간이 추가로 필요
  
  
• 연산 시간
• 연산 시간은 정렬할 원소의 수 n 과 키 값의 자릿수 d 와 버킷의 수를 결정하는 기수 r 에 따라 달라진다.
  - 정렬할 원소 n 개를 r 개의 버킷에 분배하는 작업 : (n+r)
  - 이 작업을 자릿수 d 만큼 반복
  
  
• 수행할 전체 작업 : d(n+r)
• 시간 복잡도 : O(d(n+r))

힙 정렬(Heap Sort)

• 고급 정렬 알고리즘(병합 정렬, 퀵 정렬, 힙 정렬) 중 하나.
  
  먼저, 힙 정렬을 알아보기 전에 힙 정렬에 필요한 이진 트리(Binary Tree)의 개념 부터 알고 넘어가자.
  
  
• 이진 트리(Binary Tree)
  
  
• 최대 두 개까지의 자식 노드를 가질 수 있는 트리
• 하나의 노드는 0, 1 혹은 2개의 서브 트리를 가질 수 있다.
• 좌 서브 트리(Left Subtree)
• 우 서브 트리(Right Subtree)
  
  
• 널 트리(Null tree)
  - 어떠한 노드도 가지고 있지 않은 트리

• 포화 이진 트리(Full Binary Tree)
  
  
• 높이 h 인 이진 트리에서 모든 단말 노드가 레벨 h 에 있는 트리
• 최대 노드 수 :

• 완전 이진 트리(Complete Binary Tree)
  
  
• 높이(h-1)까지는 포환 이진트리 이고, 마지막 레벨 h에서, 왼쪽에서 오른쪽으로 단말 노드를 채운 것

• 편향 이진 트리(Skewed Binary Tree)
  
  
• 이진 트리 중에서 최소 개수의 노드를 가지면서 왼쪽이나 오른쪽 서브 트리만 가지고 있는 트리

• 이진 트리의 순차 자료구조 표현
  
  
• 완전 이진 트리의 배열 표현 방법

• 이진 트리의 순차 자료구조 표현
  
  
• 편향 이진 트리의 배열 표현 방법

그럼 이제 힙(Heap)에 대해서 알아 보자.

• 힙(Heap)
  
  
• 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조
  
  
• 최대 힙(Max Heap)
• 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 같은 크기의 관계
  - ( 부모 노드의 키 값 ≥ 자식 노드의 키 값 ) 의 관계를 가지는 노드들의 완전 이진 트리
  
  
• 최소 힙(Min Heap)
• 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작거나 같은 크기의 관계
  - ( 부모 노드의 키 값 ≤ 자식 노드의 키 값 ) 의 관계를 가지는 노드들의 완전 이진 트리
  
  
• 힙(Heap)의 예

• 힙(Heap)이 아닌 예

• 힙 정렬(Heap Sort)의 개념
  
  
• 힙 자료구조를 이용한 정렬 방법
  
  
• 힙(Heap)에서 항상 가장 큰 원소가 루트 노드가 되고 삭제 연산을 수행하면 항상 루트 노드의 원소를 삭제하여 반환
• 최대 힙에서 대해서 원소의 개수만큼 삭제 연산을 수행하여 내림차순으로 정렬 수행
• 최소 힙에 대해서 원소의 개수만큼 삭제 연산을 수행하여 오름차순으로 정렬 수행
  
  
• 힙 정렬(Heap Sort) 수행 방법
  1. 정렬한 원소들을 입력하여 최대 힙 구성
  2. 힙에 대하여 삭제 연산을 수행하여 얻은 원소를 마지막 자리에 배치
  3. 나머지 원소에 대해서 다시 최대 힙로 재구성
       원소의 개수만큼 2~3을 반복 수행
  

• 힙 정렬 수행 과정
  
  
• 정렬되지 않은 [69, 10, 30, 2, 16, 8, 31, 22]의 자료들을 힙 정렬 방법으로 정렬하는 과정을 살펴보자.
• 초기 상태 : 정렬할 원소가 8개 이므로 노드가 8개인 완전 이진 트리를 만들고, 최대 힙(Max Heap)으로 구성함

(최대힙 구성시 우측 서브트리의 숫자 20 >> 30 임을 알려드립니다.)

1. 힙에 사제 연산을 수행하여 루트 노드의 원소 69를 구해서 배열의 마지막 자리에 저장한다.

나머지 원소들에 대해서 최대 힙으로 재 구성함

2. 힙에 삭제 연산을 수행하여 루트 노드의 원소 31을 구해서 배열의 비어있는 마지막 자리에 저장한다.

나머지 원소들에 대해서 최대 힙으로 재 구성함

3. 힙에 삭제 연산을 수행하여 루트 노드의 원소 30을 구해서 배열의 비어있는 마지막 자리에 저장한다.

나머지 원소들에 대해서 최대 힙으로 재 구성함

4. 힙에 삭제 연산을 수행하여 루트 노드의 원소 22를 구해서 배열의 비어있는 마지막 자리에 저장한다.

나머지 원소들에 대해서 최대 힙으로 재 구성함

5. 힙에 삭제 연산을 수행하여 루트 노드의 원소 16을 구해서 배열의 비어있는 마지막 자리에 저장한다.

나머지 원소들에 대해서 최대 힙으로 재 구성함

6. 힙에 삭제 연산을 수행하여 루트 노드의 원소 10을 구해서 배열의 비어있는 마지막 자리에 저장한다.

나머지 원소들에 대해서 최대 힙으로 재 구성함

7. 힙에 삭제 연산을 수행하여 루트 노드의 원소 8을 구해서 배열의 비어있는 마지막 자리에 저장한다.

나머지 원소들에 대해서 최대 힙으로 재 구성함

8. 힙에 삭제 연산을 수행하여 루트 노드의 원소 2을 구해서 배열의 비어있는 마지막 자리에 저장한다.

나머지 원소들에 대해서 최대 힙으로 재 구성함

• 힙 정렬 알고리즘 분석
  
  
• 메모리 사용공간
• 원소 n개에 대해서 n개의 메모리 공간 사용
• 크기 n의 힙 저장 공간
  
  
• 연산 시간
• 힙 재구성 연산 시간
  - n개의 노드에 대해서 완전 이진 트리는 log₂(n+1)의 레벨을 가지므로 완전 이진 트리를 힙으로 구성하는 평균 시간은 O(log n)
  - n개의 노드에 대해서 n번의 힙 재구성 작업 수행
  
• 평균 시간 복잡도 : O(n log n)
  

  
  

삽입 정렬(Insert Sort)

• 기초적인 정렬 알고리즘(선택 정렬, 버블 정렬, 삽입 정렬)중 하나.
  
  
• 수행 방법
• 정렬 되어있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방법
  
  
• 정렬할 자료를 두 개의 부분집합 S와 U로 가정
• 부분집합 S : 정렬된 앞부분의 원소들
• 부분집합 U : 아직 정렬되지 않은 나머지 원소들
• 정렬되지 않은 부분집합 U의 원소를 하나씩 거내서 이미 정렬되어있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입
• 삽입 정렬을 반복하면서 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 감소하게 한다. 부분 집합 U가 공집합이 되면 삽입 정렬이 완성된다.
  
  
• 삽입 정렬 수행 과정
• 정렬 되지 않은 [ 69, 10, 30, 2, 16, 8, 31, 22 ]의 자료들을 삽입 정렬 방법으로 정렬하는 과정을 살펴보자.
• 초기 상태 : 첫 번째 원소는 정렬되어있는 부분 집합 S로 생각하고 나머지 원소들은 정렬되지 않은 원소들의 부분 집합 U로 생각한다.
  S=[69], U=[10, 30, 2, 16, 8, 31, 22]

1. U의 첫 번째 원소 10을 S의 마지막 원소 69와 비교하여 (10 < 69)이므로 원소 10은 원소 69의 앞자리가 된다. 더 이상 비교할

     S의 원소가 없으므로 찾은 위치에 원소 10을 삽입한다.

     S = [10, 69], U = [30, 2, 16, 8, 31, 22]

2. U의 첫 번째 원소 30을 S의 마지막 원소 69와 비교하여 (30 < 69)이므로 원소 69의 앞자리 원소 10과 비교한다. (30 > 10)이므로

    원소 10과 69 사이에 삽입한다.

     S = [10, 30, 69], U = [2, 16, 8, 31, 22]

3. U의 첫 번째 원소 2을 S의 마지막 원소 69와 비교하여 (2 < 69)이므로 원소 69의 앞자리 원소 30과 비교하고,  (2 < 30)이므로

     다시 그 앞자리 원소 10과 비교하는데, (2 < 10)이면서 더 이상 비교할 S의 원소가 없으므로 원소 10의 앞에 삽입한다.

     S = [2, 10, 30, 69], U = [16, 8, 31, 22]

4. U의 첫 번째 원소 16을 S의 마지막 원소 69와 비교하여 (16 < 69)이므로 그 앞자리 원소 30과 비교한다.  (16 < 30)이므로

     다시 그 앞자리 원소 10과 비교하여, (16 > 10)이므로 원소 10과 30 사이에 삽입한다.

     S = [2, 10, 16, 30, 69], U = [8, 31, 22]

5. U의 첫 번째 원소 8을 S의 마지막 원소 69와 비교하여 (8 < 69)이므로 그 앞자리 원소 30과 비교한다. (8 < 30)이므로 그 앞자리

    원소 10과 비교하여, (8 < 10)이므로 다시 그 앞자리 원소 2와 비교하는데, (8 > 2)이므로 원소 2와 10사이에 삽입한다.

    S = [2, 8, 10, 16, 30, 69], U = [31, 22]

6. U의 첫 번째 원소 31을 S의 마지막 원소 69와 비교하여 (31 < 69)이므로 그 앞자리 원소 30과 비교한다. (31 > 30)이므로 원소30과

     69 사이에 삽입한다.

    S = [2, 8, 10, 16, 30, 31, 69], U = [22]

7. U의 첫 번째 원소 22를 S의 마지막 원소 69와 비교하여 (22 < 69)이므로 그 앞자리 원소 31과 비교한다. (22 < 31)이므로 그앞자리

     원소 30과 비교한다. (22 < 30)이므로 다시 그 앞자리 원소 16과 비교하여, (22 > 16)이므로 원소 16과 30사이에 삽입한다.

     S = [2, 8, 10, 16, 22, 30, 31, 69], U = []

• 삽입 정렬 알고리즘

• 삽입 정렬 알고리즘의 분석
• 메모리 사용공간
• n개의 원소에 대하여 n개의 메모리 사용
  
  
• 연산 시간
• 최선의 경우 : 원소들이 이미 정렬되어 있어서 비교횟수가 최소인 경우
  - 이미 정렬되어있는 경우에는 바로 앞자리 원소와 한번만 비교한다.
  - 전체 비교횟수 = n-1
  - 시간 복잡도 : O(n)
• 최악의 경우 : 모든 원소가 역순으로 되어있어서 비굣횟수가 최대인 경우
  - 전체 비교횟수 = 1+2+3+...+(n-1) = n(n-1)/2
  - 시간 복잡도 : O(n²)
• 삽입 정렬의 평균 비교횟수 = n(n-1)/4
• 평균 시간 복잡도 : O(n²)

  
  

정렬의 기본 개념

• 정렬(Sort)의 개념
• 순서 업이 배열되어 있는 자료들을 재 배열 하는 것
• 오름차순(ascending)
• 내림차순(descending)

• 정렬의 대상
• 레코드
• 정렬의 기준
• 정렬 키(Sort Key)필드
  
  
• 정렬방법의 분류
• 실행 방법에 따른 분류
• 비교식 정렬(comparative sort)
  - 비교하고자 하는 각 키 값들을 한번에 두 개씩 비교하여 교환함으로써 정렬을 실행하는 방식
  
  
• 분산식 정렬(distribute sort)
  - 키 값을 기준으로 하여 자료를 여러 개의 부분집합으로 분해하고, 각 부분집합을 정렬함으로써 전체를
      정렬하는 방식
  
  
• 정렬방법의 분류
• 정렬 장소에 따른 분류
• 내부 정렬(Internal sort)
• 컴퓨터 메모리 내부에서 정렬
• 정렬 속도는 빠르지만 자료의 양이 메인 메모리의 용량에 따라 제한된다.
• 내부 정렬 종류
  - 교환 방식 : 키를 비교하고 교환하여 정렬(선택정렬, 버블정렬, 퀵정렬)
  - 삽입 정렬 : 키를 비교하고 삽입하여 정렬(삽입정렬, 셀정렬)
  - 병합 정렬 : 키를 비교하고 병합하여 정렬(2-way 병합, n-way 병합)
  - 분배 방식 : 키를 구성하는 값을 여러 개의 부분집합에 분배하여 정렬(기수 정렬)
  - 선택 방식 : 이진 트리를 사용하여 정렬(힙 정렬, 트리 정렬)
  
  
• 외부 정렬(external sort)
• 메모리의 외부인 보조 기억 장치에서 정렬
• 내부 정렬로 처리할 수 없는 대용량의 자료를 정렬
• 병합 방식 : 파일을 부분 파일로 분리하여 각각을 내부 정렬 방법으로 정렬하여 병합
                         (2-way병합, n-way병합)