[파이썬 알고리즘 인터뷰][정렬] 색 정렬

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

[0,1,2] 중 하나의 값인 배열을 in-place sort하기

 

책에서 구현된 코드

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        red, white, blue = 0, 0, len(nums)

        while white < blue:
            if nums[white] < 1:
                nums[red], nums[white] = nums[white], nums[red]
                white += 1
                red += 1
            elif nums[white] > 1:
                blue -= 1
                nums[white], nums[blue] = nums[blue], nums[white]
            else:
                white += 1

 

기억해야할 기법

• 투 포인터 활용 정렬
  
  • 현재 탐색하는 값이 1보다 작으면 left와 교환
  • 현재 탐색하는 값이 1보다 크면 right와 교환
• while문의 else에 index += 1
  • 내가 구현한 방식은 while True가 있어 위험하고 지저분해보임

 

내가 구현한 코드

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        l = 0
        r = len(nums) - 1
        for i in range(len(nums)):
            while True:
                num = nums[i]
                if l < i and num < 1:
                    nums[l], nums[i] = num, nums[l]
                    l+=1
                elif i < r and num > 1:
                    nums[r], nums[i] = num, nums[r]
                    r-=1
                else:
                    break


# quicksort에 응용
def quicksort(A, lo, hi):
    def partition(lo, hi):
        # pivot = A[hi]
        pivot = A[lo]
        left = i = lo
        right = hi
        while i <= hi:
            if left < i and pivot > A[i]:
                A[left], A[i] = A[i], A[left]
                left += 1
            elif i < right and pivot < A[i]:
                A[right], A[i] = A[i], A[right]
                right -= 1
            else:
                i+=1
        
        return left

    if lo < hi:
        pivot = partition(lo, hi)
        quicksort(A, lo, pivot-1)
        quicksort(A, pivot+1, hi)

• quicksort 개선에 적용할 수 있다고해서 적용해봤다
• while i <= hi를 뭔가 더 효율적으로 바꿀 수 있지 않을까?
  
  • right 이후의 값들은 pivot보다 크다는게 보장이 되는 점을 활용하고싶다
  • [:left]
    - pivot보다 작은 값을 보장
  • [left:right]
    - pivot과 같은 값을 보장
  • [right+1:]
    - pivot보다 큰 값을 보장
  • 문제는 return할 pivot의 위치
    - right가 --되서 i와 만났다 -> [i:]가 pivot보다 크다
    - i가 ++되서 right와 만났다 -> i의 값을 판단해봐야 안다
  • 따라서 while <= right를 해야하는지, while < right를 해야하는지 어렵다
  • 나중에 다시 보자
• +) pivot을 high부터 시작하니까 문제가 있다
  • [0, 3, 4]일 때, pivot=4
    - [i=0] 0 < pivot이지만, left < i는 아니므로 left =0
    - [i=1] 3 < pivot이므로, left와 i의 자리를 바꿈 -> [3, 0, 4]
  • 따라서 left내에서의 순서도 보장 받으려면 첫번째 값이 pivot이어야 한다