분할 정복 알고리즘 리뷰
합병정렬(Merge sort)과 퀵소트(Quick sort) 비교 분석
실무에서는 잘 안 쓰이지만, 정렬 알고리즘은 프로그래밍의 기본기를 연습하는데 적합한 알고리즘이라고 한다. 하지만 코딩 테스트에서는 면접관조차도 출제를 꺼려하는 알고리즘 중 하나(특히, 버블 정렬)라고 한다. 그럼에도 불구하고, 본인은 30년 대계의 보안 엔지니어 및 개발자(DevSecOps)가 되기 위해 오늘도 분할 정복(Divide and Conqure) 알고리즘의 한 종류인 합병 정렬 알고리즘부터 리뷰한다.
Merge sort는 리스트의 원소들을 일단 반(mid)으로 계속 쪼개기를 시작한다. 분할하는 동작을 구현한 함수가 아래 동영상의 소스에서 merge(left, right) 함수에 해당한다. 아래와 같이 총 7개의 원소를 가진 리스트라면 일단 왼쪽에 세 개, 오른쪽에 네 개로 나눈다. 한 개가 남을 때까지 나뉜 뒤, 작은 원소를 왼쪽으로 보내면서 합치기 시작한다. 이것을 병합 혹은 합병이라고 하는데, 최적화 알고리즘의 개념인 분할-정복*이 여기에 해당한다.
프로그래밍의 정석 파이썬(도경구, 2021)이 합병 정렬 과정을 도식화하면 위와 같고, 이 알고리즘을 파이썬에서 디버깅(함수 실행 추적)하면 아래 동영상과 같다.
반면에 퀵 정렬(Quick Sort)은 합병 정렬과 달리 반으로 쪼개지 않고, 기준 원소(pivot)를 임의로 선택해서 이 원소보다 작으면 앞으로 보내고, 적으면 뒤로 보내면서 쪼갠다. 분할할 때 이미 숫자를 차례대로 정렬하기 때문에 합병 정렬처럼 다시 합치는 수고를 할 필요가 없다. 하지만, 임의의 중심값인 피봇을 고를 때, 리스트를 균등하게 반으로 나누면 퀵 정렬의 성능이 가장 좋아진다는 측면과 비교해서 합병 정렬이 느리지만 더 안정적(Stable Sort)이다. 이 덕분에 퀵 정렬로도 풀리지 않던 문제가 오히려 병합 정렬로는 잘 풀리는 경우가 있어 후자가 상용 라이브러리에 많이 쓰인다고 한다.
그래서 퀵 정렬은 최대한 균등하게 리스트를 나누어지도록 피봇 값을 잘 고르는 작업이 중요한데 여기서는 이 작업은 생략하고 코딩한 소스가 아래와 같다.
퀵 정렬 함수에서 partition이라는 함수의 동작이 중요한데 디버깅 과정을 추적해도 여간 헷갈리는 게 아니다. 이 함수는 pivot(중심값) 보다 작은 원소와 큰 원소를 각각 따로 별도의 리스트로 모은 다음 튜플로 묶어서 반환한다(도경구, 2021). 즉, partition 함수의 임무는 둘째 인수인 리스트 xs를 pivot을 기준으로 작은 원소, 작지 않은 원소로 분류하여 별도의 리스트에 모아주는 것이다. 퀵 정렬 함수를 도식화하면 아래의 그림과 같다. 이것의 동작을 머릿속으로 그릴 수 있다면 위의 퀵 정렬 함수의 디버깅 과정이 어떻게 이루어지는지 하나씩 꼼꼼히 확인할 수 있다.
프로그래밍의 정석 파이썬(도경구, 2021)마지막에 합병 정렬 알고리즘의 merge 함수의 최종 리턴 값(xs + left + right)과 달리 퀵 정렬 알고리즘의 partition 함수는 크기 순으로 정렬이 안되어 반환(left: [1, 2] right: [4, 5, 9, 5, 8])된 거 같으나, pivot이 3 → 1 → 4 → 7 → 5 → 5 → 9 → 8의 순으로 고정되는 튜플(변하지 않는 값, 비가역성)로 던져줬기 때문에 위의 도식에서 보이는 마지막 진한 사각형의 튜플(메모리 상태, 로컬 메모리에 임시로 저장되어 있음)들처럼 좌우로 분할(partition-swapping**) 하여 left(pivot보다 적은 값)와 right(pivot보다 큰 값)으로 나눠서 quickSort 함수로 인자 값을 전달한다. 마지막으로 다시 quickSort함수에서 크기 순으로 정렬되어 있는 있는 튜플 값을 그대로 출력한다.
partition 함수 실행 추적으로 xs 리스트의 각 선두 원소를 남겨둔다는 의미(재귀 구조)에 주목한다. (4) [프로그래밍의 정석 : 파이썬] 5-2-4. 퀵 정렬 - YouTube
분할-정복* : 재귀를 활용하는 대표적인 알고리즘이기도 하며, 이 같은 알고리즘 디자인 패러다임은 중급 이상의 코딩 테스트 문제로 빈번히 출제된다고 한다. 또한 최적 부분 구조(Optimal Substructure)를 풀이하는 매우 중요한 기법 중 하나이므로 잘 숙지해둘 필요가 있다고 한다.
partition-swapping** : 다음 섹션에서 퀵 정렬 함수를 더 간결한 코드로 짤 수 있는 알고리즘을 리뷰하면서 인용할 용어다.
참조
1) 도경구 (2021). 제어 구조의 설계 원리를 중심으로 배우는 프로그래밍의 정석 파이썬.
