[문제 해결 알고리즘] 정렬 알고리즘 ②

1. 쉘 정렬

(1) 정의

-  배열 뒷부분의 작은 숫자를 앞부분에 빠르게 이동시키고, 동시에 앞부분의 큰 숫자는 뒷부분으로 이동시킨 후, 가장 마지막에 삽입 정렬을 수행하는 알고리즘

(2) 아이디어

- 예시 데이터 : 30 60 90 10 40 80 40 20 10 60 50 30 40 90 80 

- 간격(Gap)이 5가 되는 숫자끼리 그룹 생성 : [30 80 50] [60 40 30] [90 20 40] [10 10 90] [40 60 80] 

- 그룹 별로 삽입 정렬을 수행 : [30 50 80] [30 40 60] [20 40 90] [10 10 90] [40 60 80]

  = 원래 자리 기준으로 보면 30 30 20 10 40 50 40 40 10 60 80 60 90 90 80

  > 큰 숫자는 뒷 쪽 그룹에, 작은 숫자는 앞 쪽 그룹에 있는 것을 확인할 수 있음

- 이 후 간격을 5보다 작게 해가며, 더 진행 시 삽입 정렬 수행이 더 빨라짐

- 마지막에는 반드시 간격을 1로 놓고 수행함 = 삽입 정렬

(3) 알고리즘

ⓐ for each gap h = [h0 > h1 > ... > hk = 1]

ⓑ for i = h to n -1 {

ⓒ CurrentElement = A[i]

ⓓ j = i

ⓕ while(j>=h) and A[j-h] > CurrentElement {

ⓖ A[j] = A[j-h]

ⓗ j = j-h }

ⓘ A[j] = CurrentElement }

ⓙ return 배열 A

(4) 특징

- 쉘 정렬의 수행 속도는 간격 설정에 따라 좌우됨

  : 지금까지 알려진 가장 좋은 성능을 가진 간격 = 1, 4, 10, 23, 57, 132, 301, 701 (이후로는 밝혀지지 않음)

- 쉘 정렬의 시간 복잡도는 아직 풀리지 않은 문제임

- 최악의 경우 O(n^2)

- 히바드(Hibbard)의 간격(2^k-1)을 사용하는 경우 시간 복잡도 : O(N^(1.5))

- 많은 실험을 통해 쉘 정렬의 시간 복잡도는 O(n^(1.25))로 알려짐

2. 힙 정렬

(1) 정의

- 힙 : 힙 조건을 만족하는 완전 이진 트리

- 힙 조건 : 각 노드의 값이 자식 노드의 값보다 커야한다는 것

- 노드의 값은 우선순위라고 함

- 힙의 루트에는 가장 높은 우선순위가 저장됨

  (값이 작을수록 우선순위가 높은 경우에는 가장 작은 값이 우선 순위에 저장)

- n개의 노드를 가진 힙은 완전 이진 트리이므로 힙의 높이가 log(2)n이며 노드들은 빈 공간없이 배열에 저장할 수 있음

(2) 아이디어

- 힙 정렬 :  힙 자료구조를 이용하는 정렬 알고리즘

- 오름 차순의 정렬을 위해 최대 힙을 구성함

- 힙의 루트에는 가장 큰 수가 저장되므로 루트의 숫자를 힙에 가장 마지막 노드에 있는 숫자와 바꿈

- 가장 큰 수를 배열의 가장 끝으로 이동시킨 것임

- 루트에 새로 저장된 숫자로 인해 위배된 힙 조건을 해결하여 힙 조건을 만족시키고, 힙 크기를 1개 줄임

- 이 과정을 반복하여 나머지 수사를 정렬함

(3) 알고리즘

- 입력 : A[1]부터 A[n]이 저장된 배열 A

- 출력 : 정렬된 배열 A

ⓐ 배열 A의 숫자에 대해서 힙 자료 구조를 만듦

ⓑ heapsize = n

ⓒ For i = 1 to n-1 {

ⓓ A[1]과 A[heapsize] 교환

ⓔ heapsize = heapsize -1

ⓕ Downheap() }

ⓕ return 배열 A

- Downheap

 : 루트가 r을 가지고 있다고 가정함

 : 루트의 r과 자식 노드들 중에서 큰 것을 비교하여 큰 것과 r을 바꿈

 : 다시 r을 자식 노드들 중에서 큰 것과 비교ㅛ하여 힙 조건이 위배되면 앞서 수행한대로 큰 것과 r을 교환함

 : 힙 조건이 만족될 때까지 이 과정을 반복함

(4) 특징 O(n)의 시간 복잡도를 가짐

3. 기수 정렬

(1) 정의

- 숫자를 부분적으로 비교하는 정렬 방법

- 제한적인 범위 내에 있는 숫자에 대해서 각 자릿수 별로 정렬하는 알고리즘

- 어느 비교 정렬 알고리즘보다 빠름

- 계좌 번호, 날짜, 주민등록번호 등의 대용량 상용 데이터베이스 정렬에 매우 적절함

(2) 알고리즘

- 입력 : n개의 r진수의 k자리 숫자

- 출력 : 정렬된 숫자

ⓐ for i = 1 to k

ⓑ 각 숫자의 i자리 숫자에 대해 안정한 정렬을 수행함

ⓒ return 배열 A

(3) 특징

- 안정성 : 입력에 중복된 숫자가 있을 때, 정렬된 후에도 중복된 숫자의 순서가 입력에서의 순서와 동일한 경우 정렬 알고리즘이 안정성을 가진다 함

- 시간 복잡도 : for 루프가 k번 반복함 = 한 번 루프가 수행될 때 n개의 숫자의 i자리수를 읽음,  r개로 분류하여 개수를 셈, 결과에 따라 숫자가 이동하므로 O(n+r)시간이 걸림 = O(k(n+r)) ; k나 r이 입력인 크기인 n보다 크지 않으면 O(n)임

4. 외부 정렬

(1) 정의

- 입력 크기가 매우 커서 읽고 쓰는 시간이 오래 걸리는 보조 기억 장치에 입력을 저장할 수 밖에 없는 상태에서 수행되는 정렬

- 내부 정렬(입력이 주기억장치=내부 메모리에 있는 상태에서 정렬이 수행함

- 주기억 장치의 용량이 1GB이고 입력의 크기가 100GB라면 어떤 내부 정렬 알고리즘으로도 직접 정렬 불가

- 입력을 분할하여 주 기억 장치에 수용할 만큼의 데이터에 대해서만 내부 정렬을 수행하고 그 결과를 보조 기억 장치에 일단 다시 저장함

- 100GB의 데이터를 1GB씩 주 기억 장치로 읽어들임 > 퀵 정렬과 같은 내부 정렬 알고리즘을 통해 정렬함 > 다른 보조 기억 장치에 저장함

- 반복하면 원래의 잉ㅂ력이 100개의 정렬된 블록으로 분할되어 보조 기억 장치에 저장됨

- 정렬된 블록들을 하나의 정렬된 거대한 100GB 크기의 블록으로 만드는 것임

- 이 과정은 반복적인 합병을 통해 이루어짐

- 블록들을 부분적으로 주기억 장치에 읽어들여 합병을 수행하여 부분적으로 보조 기억 장치에 쓰는 과정이 반복됨

- 1GB 두 개를 합병한 방식으로 2GB+2GB로 4GB를 합병하고 결국에는 100GB 블록 1개가 남을 때까지 반복

- 외부 정렬 알고리즘은 보조 기억 장치에서의 읽고쓰기를 최소화하는 것이 중요함

 = 보조 기억 장치의 접근 시간이 주 기억 장치의 접근 시간보다 매우 오래 걸리기 때문