알고리즘

[2. 정렬] 분할정복법(Divide and Conquer)

2021. 3. 15. 20:34
목차
  1. 1. Merge Sort(합병정렬)
  2. 1) 정렬과정
  3. 2) Merge Sort python 코드
  4. 2. Quick Sort
  5. 1) 정렬과정
  6. 2) Quick Sort Python 코드

정렬 알고리즘 종류

  • Bubble Sort, Selection Sort, Insertion Sort(간단하지만 느림)
  • Merge Sort, Quick Sort, Heap Sort(빠름)
  • Radix Sort(매우 빠름)

이 중 Merge Sort, Quick Sort, Heap Sort는 분할정복법을 적용하여 풀 수 있다.

  • 분할: 풀고자 하는 문제를 작은 크기의 동일한 문제들로 분할
  • 정복: 각각의 작은 문제들을 순환적으로 해결
  • 합병: 작은 문제의 해들을 합하여 원래 문제에 대한 답을 구함(merging)

 

1. Merge Sort(합병정렬)

1) 정렬과정

- ① 분할: 배열의 길이가 1이 될때 까지 배열을 반복적으로 반으로 나눔(n→n2→n4⋯→1)

- ② 정복: 나눠진 각 배열들을 정렬

- ③ 합병: 정렬된 두개의 배열을 합병

 

merge sort 흐름 개념도

 

2) Merge Sort python 코드

A = np.random.randint(20, size=10)
p = 0
r = len(A)-1

def merge_sort(A, p, r):
    '''
    p,q,r: 배열의 index
    분할, 정복, 합병을 거친다
    '''
    if p < r:
        q = (p+r)//2    # 분할
        merge_sort(A, p, q)    # 앞 배열 정복
        merge_sort(A, q+1, r)    # 뒷 배열 정복
        merge(A, p, q, r)
        
        return A
        
    else:
        return None
        
        
def merge(A, p, q, r):
    '''
    정렬되어 있는 두 배열 A[p,... q], A[q+1,,,r]을 병합하여
    정렬된 배열 A[p ,,, r]을 만든다
    '''
    tmp = [0]*len(A)
    i = p; j=q+1; k = p
    
    while i<=q and j<=r:
        if A[i] <= A[j]:
            tmp[k] = A[i]
            i += 1
        else:
            tmp[k] = A[j]
            j += 1
        k += 1
    while i<=q:
        tmp[k] = A[i]
        i+=1; k+=1
    while j<=r:
        tmp[k] = A[j]
        j+=1; k+=1
    
    A[p:r+1] = tmp[p:r+1]

병합 부분에서 배열의 일부만 정렬하게 되므로 배열을 global로 정의하였다.

 

 

2. Quick Sort

1) 정렬과정

⓪배열에서 정렬에 사용될 기준이 되는 값(pivot)을 선택한 후

- ①분할: pivot보다 작은 값들의 배열, pivot보다 큰 값들의 배열로 분할

- ②정복: 각 배열을 정렬한다

- ③합병: Nothing to do

 

quick sort 정렬 흐름

 

2) Quick Sort Python 코드

def quick_sort(A, p, r):
    if p<r:
        q = partition(A, p, r)  # q는 두 배열 사이에서의 pivot의 위치
        quick_sort(A, p, q-1)  # pivot 왼쪽 배열을 순환적으로 정렬
        quick_sort(A, q+1, r)   # pivot 오른쪽 배열을 순환적으로 정렬
        
        return A
        

def partition(A, p, r):
    i = p-1  # pivot보다 작은 배열 중 마지막 위치의 index
    j = p  # 현재 검사중인 값의 index
    pivot_value = A[r]
    for j in range(p, r):
        if A[j] <= pivot_value:
            i += 1
            A[i], A[j] = A[j], A[i]
    
    A[i+1], A[r] = A[r], A[i+1]
           
    return i+1
    
    
A = np.random.randint(20, size=10)
p = 0
r = len(A)-1

print(A)
>> [ 9  1  5  5 13 10 13 13  9  8]

quick_sort(A, p, r)
>> array([ 1,  5,  5,  8,  9,  9, 10, 13, 13, 13])

본 예제에서는 pivot 값을 맨 마지막 값으로 설정했으나 랜덤으로 선택해도 상관없다. 뭘 선택하든 맨 뒤로 보내서 정렬하면 같은 시간복잡도로 정렬된다.

 

 

[References]

  • 권오흠 교수, 알고리즘(강의 링크)

 

 

728x90
저작자표시 비영리 동일조건 (새창열림)

'알고리즘' 카테고리의 다른 글

[3. 검색트리] 이진트리 검색 (1)  (0) 2021.04.03
[2. 정렬] Heap Sort (1)  (0) 2021.04.01
[2. 정렬] 기본적인 정렬 알고리즘  (0) 2021.03.09
[1. 순환(Recursion)] 순환 알고리즘 설계  (0) 2021.03.06
[1. 순환(Recursion)] Recursive하게 생각하기  (0) 2021.03.03
  1. 1. Merge Sort(합병정렬)
  2. 1) 정렬과정
  3. 2) Merge Sort python 코드
  4. 2. Quick Sort
  5. 1) 정렬과정
  6. 2) Quick Sort Python 코드
'알고리즘' 카테고리의 다른 글
  • [3. 검색트리] 이진트리 검색 (1)
  • [2. 정렬] Heap Sort (1)
  • [2. 정렬] 기본적인 정렬 알고리즘
  • [1. 순환(Recursion)] 순환 알고리즘 설계
Fine애플
Fine애플
이것저것
Fine애플
끄적끄적
Fine애플
전체
오늘
어제
  • 분류 전체보기 (167)
    • 논문 및 개념 정리 (27)
    • Pattern Recognition (8)
    • 개발 (57)
    • python 메모 (45)
    • pytorch, tensorflow (5)
    • 알고리즘 (9)
    • Toy Projects (4)
    • 통계이론 (2)
    • Reinforcement Learning (10)

블로그 메뉴

  • 홈

공지사항

인기 글

태그

  • pandas
  • container
  • Docker
  • 개발환경
  • BigBird
  • Probability
  • miniconda
  • transformer
  • 알고리즘
  • ubuntu
  • nlp
  • reinforcement learning
  • 딥러닝
  • tensorflow
  • Bert
  • PyTorch
  • 자연어
  • GPU
  • python
  • 언어모델

최근 댓글

최근 글

hELLO · Designed By 정상우.
Fine애플
[2. 정렬] 분할정복법(Divide and Conquer)
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.