Python 알고리즘 _ 분할정복&퀵정렬

📍 분할정복 설계 방법 (Divide ans Conquer)

• 분할 : 문제 입력사례를 둘 이상의 작은 입력사례로 분할
• 정복 : 작은 입력 사례들을 각각 정복, 재귀호출
• 통합 : 필요하면 작은 입력 사례의 해답을 통합해 원래 해답을 도출

분할정복 vs 동적계획
하향식 / 상향식 문제풀이 방식

분할정복 vs 탐욕법
탐욕법은 가장 비효율적인 분할정복 알고리즘 > 모든 원소를 탐색

📍 퀵정렬

대표적인 분할정복 알고리즘이다.
내부정렬 : 추가 리스트를 사용하지 않음 (합병정렬과 반대)

[Divide] : 기준 원소(pivot)를 정해서 좌우 분할
[Conquer] : 왼쪽과 오른쪽 리스트를 각각 재귀적으로 퀵정렬
[Obtain] : 정렬된 리스트 리턴

💡 기준원소(pivot)는 어떻게 정하나?
편의상 리스트의 첫 원소를 기준원소로 정하자

💡 기준원소로 어떻게 나눌수 있는가?
두개의 인덱스(i,j)로 비교, 교환

✏️ 퀵정렬 코드

def quicksort(array):
    if len(array) <= 1:
        return array
    pivot = array[len(array) // 2]
    less, more, equal = [],[],[]  # 세개의 리스트 생성(작은수,같은수,큰수)
    for each in range(len(array)): 
        each = array.pop()  # 하나씩 꺼내서 비교해본다
        if each < pivot:  
            less.append(each)
        elif each > pivot:
            more.append(each)
        else: 
            equal.append(each)
    return quicksort(less) + equal + quicksort(more)  #합치기

#출력
S = [15, 22, 13, 27, 12, 10, 20, 25]
print('Before: ', S)
print('After: ', quicksort(S))

#결과
Before:  [15, 22, 13, 27, 12, 10, 20, 25]
After:  [10, 12, 13, 15, 20, 22, 25, 27]