[파이썬] 분할 정복 알고리즘

복잡하거나 큰 문제를 여러 개로 나눠서 푸는 방법이다.

특징 : 병렬적으로 문제를 해결할 수 있다.(하지만, 문제를 해결하기위해 문제해결함수가 재귀적으로 호출될 수 있으므로 메모리가 추가적으로 사용될 수 있다.)

퀵정렬

• 퀵 정렬의 시간복잡도는 최악의 경우 O(n²)이며 평균의 경우 O(nlogn)이다.
  • 최악: 피벗에 의한 원소들의 부분집합이 1개와 n-1개로 분할되는 경우가 반복되는 경우
• 병합 정렬은 성능의 저하 없이 항상 O(nlogn)이다.
  • 퀵 정렬은 불안전 정렬이고, 병합정렬은 안정 정렬이다.
  • 동일한 값에 대해 기존의 순서가 유지되는 것이 안정 정렬이다.

def quick_sort(ARRAY):
    ARRAY_LENGTH = len(ARRAY)
    if ARRAY_LENGTH <= 1:
        return ARRAY
    else:
        PIVOT = ARRAY[0]
        GREATER = [element for element in ARRAY[1:] if element > PIVOT]
        LESSER = [element for element in ARRAY[1:] if element <= PIVOT]
        return quick_sort(LESSER) + [PIVOT] + quick_sort(GREATER)

ARRAY = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(quick_sort(ARRAY))

• 배열의 길이가 1이하면 그냥 배열 리턴
• 첫번째 값을 pivot으로 설정
• 이후 요소들을 반복문으로 pivot과 비교해서 큰값들이 있는 리스트와 작은값이 있는 리스트를 만듬
• 재귀(작은값배열) + [pivot] + 재귀(큰값배열)

순서

병합정렬

def test_recur_divide(list):
    # 1. 리스트의 길이를 저장합니다.
    list_length = len(list)

    # 2. 리스트의 길이가 1이 될때까지, 즉 분할할 수 없을 때까지 아래 로직을 반복 수행합니다.
    if list_length == 1:
        return list

    # 3. 리스트의 중간 지점을 식별하고 리스트를 left_partition과 right_partition으로 분할합니다.
    mid_point = list_length // 2

    # 4. 모든 파티션이 분할할 수 없는 작은 구성 요소로 분할되도록 하려면,
    # 아래처럼 test_recur_divide 함수가 재귀적으로 호출됩니다.
    # test_recur_divide 함수 안에 매개변수는 두가지로 나뉘어서 전달됩니다.

    # left_partition은 리스트의 0번째 인덱스부터 중간지점 인덱스까지의 값을 전달받고,
    # right_partition은 리스트의 (중간지점+1)번째 인덱스부터 마지막지점 인덱스까지의 값을 전달받습니다.
    left_partition = test_recur_divide(list[:mid_point])
    right_partition = test_recur_divide(list[mid_point:])

    # 5. test_recur_divide 함수는 정렬된 왼쪽과 오른쪽 파티션으로 구성된 리스트를 반환합니다.
    return test_sort_combine(left_partition, right_partition)

병합정렬 알고리즘을 구현하는 접근 방식은 두 부분으로 나뉩니다.

첫 번째 부분은 분할정복 방법의 분할 구성 요소를 수행합니다.

첫 번째 부분에서의 주요 코드구현은 초기 리스트를 더 작은 구성 요소로 나눕니다.

초기 리스트 분할은 분리된 각 구성 요소를 더 이상 분할할 수 없는 경우에만 중지됩니다.

# 6. 두 개의 리스트를 받아 두 리스트 내의 요소로 정렬된 리스트를 반환합니다.
def test_sort_combine(left, right):
    # 7. 정렬된 결과값으로 채워질 비어있는 리스트변수 output을 초기화합니다.
    # 리스트를 반복할 때 사용되는 두 개의 변수 i와 j를 초기화합니다.
    output = []
    i = j = 0

    # 8. 두 변수 i와 j가 왼쪽과 오른쪽 리스트의 길이보다 작으면 while 루프를 실행합니다.
    while i < len(left) and j < len(right):
        # 9. 각 반복 동안 두 리스트의 모든 위치에 있는 요소를 비교합니다.
        if left[i] < right[j]:
            # 오름차순으로 정렬하기위해 output변수에는 더 작은 값으로 채워집니다.
            output.append(left[i])
            # 10. 변수 i값을 +1 함으로써 오른쪽으로 한칸 이동시킵니다.
            i += 1
        else:
            output.append(right[j])
            j += 1
    # 11. 남아있는 리스트 요소에서 현재 i, j 값을 기준으로 각각 리스트의 마지막지점 인덱스까지 값을 넣고 결과값을 반환합니다.
    output.extend(left[i:])
    output.extend(right[j:])

    return output