[Python]전략패턴

목차

 

이전 글에서 자바에서의 전략패턴 구현에 대해 알아본 적이 있다.

 

[Java]전략패턴

[Java]전략패턴

 

그 이후로 이런저런 구현을 하다가, 파이썬을 이용해 개발을 해야 할 일이 생겼는데,

 

아예 처음부터 전략패턴을 적용해서 구조를 설계하면 좋을 것 같다는 생각이 들어서 공부하게 되었다.

 

이 글에서는 위의 글과 마찬가지로 정렬 로직을 이용해 전략패턴을 구현하는 법을 살펴본다.

 

각 구현에 대한 세부사항은 아래 글에 적혀있다:

 

[Java+Python]삽입 정렬(Insert Sort)

[Java+Python]버블 정렬(Bubble Sort)

[Java+Python]선택 정렬(Selection Sort)

[Java+Python]병합 정렬(Merge Sort)

[Java+Python]힙 정렬(Heap Sort)

[Java+Python]퀵 정렬(Quick Sort)

[Java+Python]카운팅 정렬(Counting Sort)

 

추가로 이 글을 따라오기 위한 프로젝트 구조는 대략 아래와 같다.

 

이 글에서는 퀵 정렬과 병합 정렬에 대해서만 다루기 때문에 나머지는 없어도 된다.

 

Sort Strategy

 

가장 먼저, 모든 전략이 구현해야 할 메서드를 가진 인터페이스를 정의한다. abc를 이용하면 된다.

from abc import ABC, abstractmethod


class SortStrategy(ABC):
    @abstractmethod
    def sort(self, lst):
        pass

여기서 마지막의 pass는 말 그대로 아무것도 하지 않는다는 뜻이다.

 

그 이유는 조금 당연하게도 추상 메서드의 경우 세부내용이 필요하지 않기 때문인데,

 

해당 바디가 없으면 문법 오류가 발생하므로 pass를 사용해 빈 상태를 유지하는 것이다.

 

Quick Sort

 

다음으로는, 이전에 구현해 둔 정렬을 전략으로 사용하기 위해 모양을 좀 다듬어준다.

 

별 특별한 건 아니고, 기존 구현을 기반으로 파이썬 클래스를 생성해 주면 된다.

from Sort_Impl.sort_strategy import SortStrategy


class QuickSortStrategy(SortStrategy):
    def sort(self, lst):
        self._quick_sort(lst, 0, len(lst) - 1)

    def _swap(self, lst, i, j):
        temp = lst[i]
        lst[i] = lst[j]
        lst[j] = temp

    def _partition_step(self, lst, lo, hi):
        left = lo
        right = hi
        pivot = lst[lo]

        while left < right:
            # pivot 보다 작은 값을 만날 때까지 right -= 1;
            while lst[right] >= pivot and left < right:
                right -= 1
            # pivot 보다 큰 값을 만날 때까지 left += 1;
            while lst[left] <= pivot and left < right:
                left += 1
            # 값을 찾으면 스왑. 못 찾으면 left = right 인 곳에서 자체 스왑
            self._swap(lst, left, right)

        # left = right 인 원소와 pivot 교환
        self._swap(lst, lo, left)
        # pivot 이 옯겨간, 즉 정렬된 곳의 인덱스 반환
        return left

    def _quick_sort(self, lst, lo, hi):
        # 대상 배열의 크기가 1 이하일 경우 탈출
        if lo >= hi:
            return

        # Partition Step 진행
        pivot = self._partition_step(lst, lo, hi)

        # 정렬이 끝난 pivot 기준으로 배열 쪼개서 재귀호출(왼쪽)
        self._quick_sort(lst, lo, pivot - 1)
        # 정렬이 끝난 pivot 기준으로 배열 쪼개서 재귀호출(오른쪽)
        self._quick_sort(lst, pivot + 1, hi)

클래스 내부에서 메서드를 선언하려면 self가 필요하며, 앞의 언더스코어(_)는 내부에서만 사용되는,

 

혹은 보호된 메서드를 나타내는 파이썬 컨벤션이다.

 

Merge Sort

 

계속해서 병합 정렬이다. 마찬가지 규칙으로 구성하면 된다.

from Sort_Impl.sort_strategy import SortStrategy


class MergeSortStrategy(SortStrategy):
    def sort(self, lst):
        temp = [0] * len(lst)
        self._merge_sort(lst, 0, len(lst) - 1, temp)

    def _merge_sort(self, list, start, end, temp):
        if start >= end:
            return  # 최소단위까지 쪼개면 리턴

        mid = (start + end) // 2  # 주어진 요소의 중간 값을 찾는다

        self._merge_sort(list, start, mid, temp)  # 왼쪽 절반에 대해 재귀호출
        self._merge_sort(list, mid + 1, end, temp)  # 오른쪽 절반에 대해 재귀호출. 왼쪽 절반이 모두 끝난 뒤에 호출된다.

        ########################
        # 쪼개기 끝났으니 합치기 시작 #
        ########################

        left = start  # 왼쪽 조각의 시작점
        right = mid + 1  # 오른쪽 조각의 시작점
        idx = left  # 비교후 temp에 채워넣을 인덱스

        while left <= mid and right <= end:
            ###########################################################
            # 왼쪽 조각의 left번째 요소가 오른쪽 조각의 right번째 요소보다 작을 경우 #
            # temp의 idx에 left번째 요소를 삽입한 뒤 left와 idx += 1         #
            ###########################################################
            if list[left] <= list[right]:
                temp[idx] = list[left]
                idx += 1
                left += 1
            # 반대의 경우 right번째 요소로 동일한 작업 수행
            else:
                temp[idx] = list[right]
                idx += 1
                right += 1
        ###########################################################
        # 왼쪽 조각의 요소가 먼저 떨어졌을 경우(left > mid)                #
        # 오른쪽 조각은 아직 남아있기 때문에 순서대로 나머지를 채워넣는다.        #
        # 비교하지 않고 채워넣는 이유는 모든 조각은 이미 정렬이 끝난 상태이기 때문! #
        ###########################################################
        if left > mid:
            while right <= end:
                temp[idx] = list[right]
                idx += 1
                right += 1
        # 반대의 경우
        else:
            while left <= mid:
                temp[idx] = list[left]
                idx += 1
                left += 1

        # 병합이 모두 끝나면 temp를 리스트에 넣어준다.
        for i in range(start, end + 1):
            list[i] = temp[i]

기존의 구현을 수정하지 않고 그대로 사용하다 보니 코드가 좀 길고 지저분하다.

 

그래도 뭐, 지금은 그게 문제가 아니니까.

 

Sorter

 

이어서 전략을 사용, 혹은 주입하는 클래스 Sorter를 만든다. 메인 함수에선 이를 이용해 패턴을 설정한다.

from Sort_Impl.sort_strategy import SortStrategy


class Sorter:
    def __init__(self, strategy: SortStrategy):
        self._strategy = strategy

    def set_strategy(self, strategy: SortStrategy):
        self._strategy = strategy

    def sort(self, lst):
        self._strategy.sort(lst)

 

Main

 

마지막으로 코드를 실행할 메인 함수이다. 각 정렬을 한 번씩 주입해 결과를 뽑는다.

from Sort_Impl.quick_sort import QuickSortStrategy
from Sort_Impl.merge_sort import MergeSortStrategy
from sorter import Sorter

lst = [4, 16, 31, 5, 4, 17, 1, 10, 15, 3, 16, 6, 7, 2, 2, 1, 5, 13, 17, 14, 4, 0]

sorter = Sorter(QuickSortStrategy())
sorter.sort(lst)
print("Quick Sort: ", lst)

sorter.set_strategy(MergeSortStrategy())
sorter.sort(lst)
print("Merge Sort: ", lst)

Quick Sort:  [0, 1, 1, 2, 2, 3, 4, 4, 4, 5, 5, 6, 7, 10, 13, 14, 15, 16, 16, 17, 17, 31]
Merge Sort:  [0, 1, 1, 2, 2, 3, 4, 4, 4, 5, 5, 6, 7, 10, 13, 14, 15, 16, 16, 17, 17, 31]