[알고리즘]분할 정복 알고리즘

분할 정복 알고리즘 = 주어진 문제의 입력을 분할하여 문제를 해결하는 방식의 알고리즘

 

◆대표적인 분할 정복 알고리즘

 

1)합병 정렬

 

문제를 계속해서 반으로 잘르고 다시 합병시키는 정렬. 자를 수 없을 때까지 자른 후 합병 과정에서 sorting함

 

#유사코드

 

MergeSort(A,p,q) 입력:A[p]~A[q] 출력: 정렬된 A[p]~A[q] if( p<q ){ k=(p+q)/2 ->floor MergeSort(A,p,k) MergeSort(A,k+1,q) A[p]~A[k]와 A[k+1]~A[q]를 합병한다. }

 

#파이썬 소스

 

def merge_sort(a): print(a) n = len(a) # 종료 조건: 정렬할 리스트의 자료 개수가 한 개 이하이면 정렬할 필요가 없음 if n <= 1: return # 그룹을 나누어 각각 병합 정렬을 호출하는 과정 mid = n // 2 # 중간을 기준으로 두 그룹으로 나눔 g1 = a[:mid] g2 = a[mid:] merge_sort(g1) # 재귀 호출로 첫 번째 그룹을 정렬 merge_sort(g2) # 재귀 호출로 두 번째 그룹을 정렬 # 두 그룹을 하나로 병합 i1 = 0 i2 = 0 ia = 0 while i1 < len(g1) and i2 < len(g2): if g1[i1] < g2[i2]: a[ia] = g1[i1] i1 += 1 ia += 1 else: a[ia] = g2[i2] i2 += 1 ia += 1 # 아직 남아 있는 자료들을 결과에 추가 while i1 < len(g1): a[ia] = g1[i1] i1 += 1 ia += 1 while i2 < len(g2): a[ia] = g2[i2] i2 += 1 ia += 1 d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5] merge_sort(d) print(d)

 

※파이썬은 들여쓰기 꼭 지켜주시기 바랍니다.

 

2)퀵 정렬

 

피봇이라 일컫는 배열의 원소를 기준으로 피봇보다 작은 숫자들은 왼편으로, 피봇보다 큰 숫자들은 오른편에 위치하도록 분할하고, 피봇을 그 사이에 놓고 정렬이 될 때까지 반복하는 sorting이다.

 

#유사코드

 

QuickSort(A,left,right) 입력:배열 A[left]~A[right] 출력:배열A[left]~A[right] if(left<right){ 피봇 선택 A[left]와 피봇자리(p)를 바꿈. 피봇보다 작은 것은 p의왼쪽 피봇보다 큰것은 p의 오른쪽으로 옮김 QuickSort(A,left,p-1)//피봇보다 작은 그룹 QuickSort(A,p+1,right)//피봇보다 큰 그룹

 

 

#파이썬 소스

 

def quick_sort_sub(a, start, end): # 종료 조건: 정렬 대상이 1개 이하면 정렬할 필요 없음 if end - start <= 0: return # 기준 값을 정하고 기준 값에 맞춰 리스트 안에서 각 자료의 위치를 맞춤 # [기준 값보다 작은 값들, 기준 값, 기준 값보다 큰 값들] pivot = a[end] # 편의상 리스트의 마지막 값을 기준 값으로 정합 i = start for j in range(start, end): if a[j] <= pivot: a[i], a[j] = a[j], a[i] i += 1 a[i], a[end] = a[end], a[i] # 재귀 호출 부분 quick_sort_sub(a, start, i - 1) # 기준 값보다 작은 그룹을 재귀 호출로 다시 정렬 quick_sort_sub(a, i + 1, end) # 기준 값보다 큰 그룹을 재귀 호출로 다시 정렬 # 리스트 전체(0 ~ len(a)-1)를 대상으로 재귀 호출 함수 호출 def quick_sort(a): quick_sort_sub(a, 0, len(a) - 1) d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5] quick_sort(d) print(d)