색 정렬 과제톡 발표 자료

1. 문제

문제는 일단 이해하기 쉽다.
그냥 배열을 오름차순으로 정렬 하라는 문제다.

2. 풀이

먼저 그냥 머리에 떠오르는 대로 풀어봤다.

def sortColors(nums: List[int]) -> None:
    i = 0
    j = i + 1
    while i < len(nums) and j < len(nums):
        if nums[i] <= nums[j]:
            j += 1
        else:
            nums[i], nums[j] = nums[j], nums[i]
            j += 1
        if j == len(nums):
            i += 1
            j = i + 1

이게 나의 첫번째 풀이다 . 무슨정렬 무슨 정렬 생각 안하고 그냥 풀었다.

두번째풀이는 오늘 배운 퀵 소트를 사용 해 봤다.

def sortColors(nums: List[int]) -> None:
    def quicksort(lst, start, end):
        def divide(part, ps, pe):
            dp = part[pe]
            i = ps - 1
            for j in range(ps, pe):
                if part[j] <= dp:
                    i += 1
                    part[i], part[j] = part[j], part[i]
            part[i + 1], part[pe] = part[pe], part[i + 1]
            return i + 1
        
        if start >= end:
            return None
        partition = divide(lst, start, end)
        quicksort(lst, start, partition - 1)
        quicksort(lst, partition + 1, end)
        return lst

    quicksort(nums, 0, len(nums) - 1)

최악의 상황이 나온 것인지 제출 후의 런타임 시간이 더 오래 걸렸다 비록
테스트 케이스가 많이 없을수도 있지만, 적어도 리트코드의 테스트 코드 에서는
느린쪽에 속해 있는것 같다.

마지막으로 버블 소트로 풀어 봤다.

 def sortColors(self, nums: List[int]) -> None:        
        iters = len(nums) - 1
        for iter in range(iters):
            wall = iters - iter
            for cur in range(wall):
                if nums[cur] > nums[cur + 1]:
                    nums[cur], nums[cur + 1] = nums[cur + 1], nums[cur]

여러 방법으로 풀었지만 일단은 이 색 정렬 문제에서 만큼은 버블 소트가 가장 빨랐다.