버블정렬 문제풀이 및 해석 (Python3)

(문제 링크)[https://leetcode.com/problems/sort-colors/]

시간 측정에 사용한 코드

def timer(fun, *args):
    st = time.perf_counter()
    result = fun(*args)
    ed = time.perf_counter()
    print(f'경과시간 {ed - st:.6f}초')
    print(result)

풀이1 (라이브러리 사용)

코드

    def sortColors(self, nums: List[int]) -> None:
        nums.sort();

해석

사실, Python3의 sort 내장 함수는 버블 정렬이 아니라 Timsort 알고리즘이다. 하지만 이렇게 아주 간단하게 순서대로 정렬할 수 있다는 점을 보여주기 위해 넣은 풀이이다. 그리고 그냥 일반적으로 정렬할때 해당 함수를 사용해서 정렬한다. 단순하게 사용하게 좋다. 또한 Timsort는 버블 정렬이 아니므로 해석은 진행하지 않았다.

풀이2 (라이브러리 x)

코드

def sortColors(self, nums: List[int]) -> None:
        r = len(nums)
        for i in range(r):
            end_range = (r - i - 1)

            for j in range(0, end_range):
                if nums[j] > nums[j+1] :
                    nums[j], nums[j+1] = nums[j+1], nums[j]

해석

우선 r 은 nums의 배열크기이다. 두 위치에서 사용하기에 r에 할당하였다. 그리고 첫번째 i for 문은 버블에서는 모든 배열을 순환하기 때문에 모두 순환한다.

하지만 두번째 j for 문은 이미 i for문에서 순회한 배열은 순회할 필요가 없다. 즉 현재 코드에서는 항상 가장 큰 수가 뒤로 갔으니, 점점 순회해야하는 최종 크기는 줄어든다. 그렇기 때문에 end_range 는 항상 (r - i - 1)의 계산식을 가진다. 가시성을 위해서 따로 빼두었다.

최종적으론 0에 배열에서부터 차례로 시작되어 두번째 for문에서는 항상 뒷배열을 순환하여 뒷배열이 더 작은 수일 경우에 앞으로 보내게된다.