[자료구조 및 알고리즘] 고급 정렬

정렬이란?

원소를 순서대로 배열하는 것

크기가 크거나 작은 순으로 정렬을 비롯하 알파벳, 생년월일 순으로 정리하는 것 모두 포함

 

정렬의 종류

- 기본정렬 : 평균적으로 n^2의 시간이 소요되는 기본적인 정렬알고리즘

- 고급정렬 : 평균적으로 nlogn의 시간이 소요되는 고급 정렬 알고리즘

- 특수정렬 : 특수한 성질을 만족하고 평균적으로 n의 시간이 소요되는 정렬 알고리즘

 

오늘 정리할 고급 정렬에는 병합 정렬, 퀵 정렬, 힙 정렬, 셀 정렬이 있다.

평균적으로 nlogn 만큼의 시간이 소요된다.

 

---

- 병합 정렬

주어진 배열을 이등분하여 각각(재귀적으로) 정렬한 다음 병합하는 정렬

 

기본원리

1. 입력된 리스트의 원소를 반으로 나눈다.

2. 전반부와 후반부를 각각 독립적으로 정렬한다.

3. 정렬된 두 부분을 병합하여 정렬된 리스트를 얻는다.

  병합 과정 : 분리된 두 리스트 각각 가장 작은 값(i,j)를 비교해 작은것부터 리스트에 할당

작동과정

1) 주어진 배열(n=10)을 반으로 나눈다

31

3

65

73

8

11

20

20

48

15

2) 각각 독립적으로 정렬

3

8

31

65

73

11

15

20

29

48

3) 병합

3(i)

8

31

65

73

11(j)

15

20

29

48

3

 

8(i)

31

65

73

11(j)

15

20

29

48

3

 

31(i)

65

73

11(j)

15

20

29

48

3

8

 

31(i)

65

73

15(j)

20

29

48

3

8

11

 

31(i)

65

73

20(j)

29

48

3

8

11

15

 

31(i)

65

73

29(j)

48

3

8

11

15

20

 

31(i)

65

73

48(j)

3

8

11

15

20

29

 

65(i)

73

48(j)

3

8

11

15

20

29

31

 

65(i)

73

3

8

11

15

20

29

31

48

 

3

8

11

15

20

29

31

48

65

73

최종배열

 

병합 정렬 약점

병합 정렬은 항상 평균 nlogn의 수행시간을 보장(비교, 옮기기 작업)

 

그러나 주어진 배열안에서 정렬하는 내부 정렬이 아니다

왜냐하면 두 리스트에서 크기를 비교해서 할당하는 새로운 별도의 공간이 필요하기 때문에  

결국 길이가 n인 리스트를 정렬하기 위해 길이가 n인 보조 배열이 필요함

 

내부정렬은 주어진 리스트 이외에 추가 공간을 사용하지 않은 정렬.

 

- 구현 코드

def mergeSort(A, p:int, r:int):     # 입력인자 리스트 A, p:시작인덱스(0) ,r:끝인덱스(len(A)-1)
	if p < r:
    	q = (p+r) // 2                      # 중간 인덱스 구하기
        mergeSort(A,p,q)                    # 왼쪽절반 정렬
        mergeSort(A,q+1,r)                  # 오른쪽 절반 정렬
        merge(A,p,q,r)                      # 병합
        
def merge(A, p:int, q:int, r:int):     # 병합 함수
	i = p               				# 왼쪽 리스트 입력시작
    j = q+1             				# 오른쪽 리스트 입력시작
    t = 0              					 # 임시 배열 인덱스
    tmp = [0 for i in range(len(A))]       # 정렬결과를 저장할 임시배열 생성
    while i <= q and j <= r:             # 왼쪽리스트와 오른쪽 리스트의 각각 가장 작은 값 비교
    	if A[i] <= A[j]:				# 왼쪽에 있는 값이 작은경우
        	tmp[t] = A[i]                # 가장 작은 값을 임시배열에 할당
            t += 1
            i += 1
        else:
        	tmp[t] = A[j]                 # 오른쪽에 있는 값이 작은경우
            t += 1                        # 가장작은 값을 임시배열에 할당
            j += 1
	while i <= q:						 # 왼쪽배열에 값이 남은경우
    	tmp[t] = A[i]                    # 남은 값을 임시배열에 할당
    	t += 1
    	i += 1
    while j <= r:                        # 오른쪽 배열에 값이 남은경우
    	tmp[t] = A[j]                     # 남은 값을 임시배열에 할당
        t += 1
        j += 1
    i = p                               # i랑 t값 초기값으로 설정
    t = 0
    while i <= r:                       # 임시배열의 값을 원래배열로 복사
    	A[i] = tmp[t] 
        t += 1
        i += 1

 

 

---

- 퀵정렬

기준 원소를 하나 잡아 기준 원소보다 작은 원소와 큰 원소 그룹으로 나누어 기준 원소의 좌우를 분할한 다음 각각 정렬하는 방법

 

병합정렬은 먼저 재귀적으로 작은 문제를 해결한 다음 후처리를 하는 데 반해, 퀵정렬은 선행 작업을 한 다음 재귀적으로 작은 문제를 해결

 

기본원리

1) 주어진 배열에서 기준원소를 정한다

2) 기준원소보다 작은 원소는 왼쪽에 나머지는 기준의 오른쪽에 재배치한다

3) 기준원소의 왼쪽과 오른쪽을 각각 독립적으로 정렬한다

 

작동과정

1) 정렬할 배열(n = 10)에서 기준원소를 정한다(여기서는 맨 끝 원소)

31

8

48

73

11

3

20

29

65

15

2) 기준원소를 기준으로 분할(파티션) - 기준원소보다 작으면 1구역, 기준원소보다 크거나 같은 원소 2구역, 미정 3구역

31

8

48

73

11

3

20

29

65

15

8

31

48

73

11

3

20

29

65

15

8

31

48

73

11

3

20

29

65

15

8

31

48

73

11

3

20

29

65

15

8

11

48

73

31

3

20

29

65

15

8

11

3

73

31

48

20

29

65

15

8

11

3

73

31

48

20

29

65

15

8

11

3

73

31

48

20

29

65

15

8

11

3

73

31

48

20

29

65

15

8

11

3

15

31

48

20

29

65

73

분할(파티션)완료

3

8

11

15

20

29

31

48

65

73

최종정렬 후 배열

 

퀵 정렬 특성

퀵정렬의 성능은 파티션의 균형이 좌우한다

최악의 경우(한쪽 파티션이 0인경우) 평균 n^2의 수행시간 > 모든 원소가 동일하면 선택정렬과 동일한 성능

최고의 경우( 좌우 파티션이 반반인 경우) 평균 nlogn의 수행시간

 

평균적으로 매우 빨라 필드에서 가장 많이 사용

같은 원소가 그룹에 있으면 그룹의 크기가 클수록 성능이 떨어짐(같은 원소들은 한쪽으로 몰리니까)

 

- 구현코드(중요)

def quickSort(A, p:int, r:int):      # 리스트 A , p: 시작 인덱스, r: 끝 인덱스
	if p < r:
    	q = partition(A,p,r)            # 분할하고 기준원소 반환
        quickSort(A,p,q-1)             # 왼쪽 부분 리스트 정렬
        quickSort(A,q+1,r)             # 오른쪽 부분 리스트 정렬
        
def partition(A, p:int, r:int):
	x = A[r]                          # 끝에 원소를 기준원소로 설정
    i = p - 1                         # 기준원소보다 작은 원소가 배치될 위치 설정
    for j in range(p,r):              # j는 기준원소보다 큰 원소가 배치될 위치 설정
    	if A[j] < x:                  # 기준원소보다 작은 경우
        	i += 1                    # 다음위치 설정
            A[i], A[j] = A[j], A[i]   # 교환
    A[i+1], A[r] = A[r], A[i+1]       # 기준원소를 파티션 중간으로 이동(교환)
    return i+1                        # 기준원소의 최종위치 반환

 

---

- 힙 정렬

 힙 정렬은 힙 자료구조를 사용해서 정렬

리스트가 주어지면 buildHeap()으로 힙을 만들기

이후 원소를 제가하면서 percolateDown()으로 힙 유지

하나씩 빼 준 값을 차례로 저장

 

기본원리

1) 주어진 리스트를 리스트를 최대힙으로 수선

2) 마지막 원소와 루트를 교환하고 마지막 원소를 관심대상에서 제외

3) 스며내리기

4) 반복

 

힙 정렬 특성

힙 정렬의 수행시간은 O(nlogn)

최악의 경우 수행시간은 평균 nlogn

최고의 경우(모든 원소가 동일한 경우, 비교만 하고 이동이 없음) 평균 n의 수행시간

 

힙정렬은 병합정렬과 달리 추가적인 공간을 요구하지 않음 또한 최악의 경우에도 평균nlogn의 수행시간을 넘지 않음

 

- 구현코드

def heapSort():
	buildHeap(A)
    for last in range(len(A)-1,0,-1):           # 관심 범위 변경
    A[last], A[0] = A[0], A[last]                   # 루트랑 마지막 값 바꾸기
    percolateDown(A,0,last-1)                  # 스며내리기 수선
    
def buildHeap(A):
	for i in range((len(A)-2)//2,-1,-1):
    	percolateDown(A,i,len(A)-1)
     
def percolateDown(A,k:int,end:int):
	child = 2*k+1
    right = 2*k+2
    if child <= end:
    	if right <= end and A[child] < A[right]:
        	child = right
        if A[k] < A[child]:
        	A[k],A[child] = A[child],A[k]
            percolateDown(A,child,end)

 

---

- 셸 정렬

셸 정렬은 삽입 정렬의 성능을 극대화 할 수 있게 한 정렬임

셸 정렬의 마지막은 삽입 정렬

삽입 정렬에서 원소의 이동 횟루를 극적으로 줄임

Why? 삽입정렬은 정렬되어 있는 원소의 정렬에서 탁월한 성능을 보이니까 평균 n의 수행시간

 

기본원리

1) 먼저 정렬해야 할 리스트를 일정한 기준에 따라 분류
2) 연속적이지 않은 여러 개의 부분 리스트를 생성
3) 각 부분 리스트를 삽입 정렬을 이용하여 정렬
4) 모든 부분 리스트가 정렬되면 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후에 알고리즘을 반복
5) 위의 과정을 부분 리스트의 개수가 1이 될 때까지 반복

 

작동과정

1) 주어진 배열(n = 10)을 일정한 기준에 따라 분류(간격 k = 3)

3

31

48

73

8

33

11

4

20

65

3

73

11

65

31

8

4

48

33

20

간격 k = 3일때 부분집합들

 

2) 각 부분집합들을 삽입정렬을 이용하여 정렬

3

11

65

73

4

8

31

20

33

48

1회전 결과

3

4

20

11

8

33

65

31

48

73

 

3) 1회전 결과를 간격 k =2 일때 분류

3

20

8

65

48

4

11

33

31

73

4) 각 부분집합들을 삽입정렬을 이용하여 정렬

3

8

20

48

65

4

11

31

33

73

2회전 결과

3

4

8

11

20

31

48

33

65

73

5) k=1일때 반복

3

4

8

11

20

31

33

48

65

73

최종배열

 

- 갭수열이란?

원소사이의 간격을 나타내는 수들의 나열

갭수열을 잡는 방법은 다양하다

ex) n/2보다 작은 어디에서 2k-1(홀수)을 만족하는 수들의 나열

 

셸 정렬의 성능은 마지막 삽입 정렬 시간을 단축시키는 정도에 비해 앞의 준비단계에 소모한 시간이 얼마나 작은가가 중요

따라서 갭수열이 중요

 

- 구현코드

def shellSort(A):
	H = gapSequence(len(A))                 # 갭수열 생성
    for h in H:                          
    	for k in range(h):                     # 간격 h에 따라 k번째 시작점부터 부분 삽입 정렬 실행
        	stepInsertionSort(A, k,h)
            
            

def stepInsertionSort(A, k:int, h:int):	
	for i in range(k+h, len(A), h):        # k부터 시작하여 간격 h씩 증가
    	j = i-h                            # 삽입할 위치의 바로 앞 원소
        newItem = A[i]                     # 현재 삽입할 원소
        while 0 <= j and newItem < A[j]:   # 삽입할 위치를 찾기 위해 역방향으로 비교
        	A[j + h] = A[j]                # 원소를 뒤로 한칸(갭만큼) 이동
            j -= h                  
        A[j+h] = newItem                   # 원소 삽입
        
 def gapSequence(n:int):                   # 간격생산기
 	H = [1] 
    gap = 1
    while gap < n/5:
    	gap = 3*gap+1
        H.append(gap)                     # 간격 추가
    H.reverse()                           # 간격 큰거부터 쓸라고 역순 정렬
    return H