algorithm | array - sort colors

> 문제

위와 같은 배열이 있는 경우 작은 수 부터 큰 수 순서로 정렬하여야 합니다.

---

> solution1_count

3개의 빈 변수를 만들어 오른쪽으로 옮겨가며 각 숫자의 갯수를 기록한 후 output으로 각각의 갯수만큼 차례대로 채운 배열을 리턴하면 됩니다.

time complexity는 O(n)가 됩니다.

---

> solution2_sort colors

in-place swap방식

3개의 포인터를 만들어 다음과 같은 규칙을 정해줍니다.
'A 포인터는 0을 받으면 오른 쪽으로 한 칸'
'B 포인터는 2를 받으면 왼쪽으로 한 칸'
'C 포인터는 오른쪽으로 이동하면서 0을 만나면 A포인터와 swap, 2를 만나면 B포인터와 swap합니다.'

C 포인터가 0을 만났기 때문에 A 포인터가 가리키는 숫자와 스왑을 합니다.
그리고 A 포인터와 B 포인터는 오른쪽으로 한 칸 이동합니다.

C 포인터가 B 포인터와 스왑을 한 경우 A 포인터와의 스왑과는 달리 C 포인터가 가리키는 숫자는 0, 1, 2 모두 가능하므로 스왑 후의 값을 다시 한 번 체크해줘야 함을 주의해야 합니다.

C 포인터가 1을 가리키는 경우 스왑 없이 오른쪽으로 이동합니다.

위와 같은 과정을 반복하면 왼쪽부터 0 ~ 2의 순서로 정렬되며 최종적으로 C 포인터와 B 포인터가 교차(C <= B)되면 operation이 종료 되도록 합니다.

time complexity는 O(n)이 됩니다.

Quick sort의 원리와 다를 바 없으며 partitioning에 대한 내용입니다.

▶︎ code

nums = [1, 0, 2, 2, 0, 1, 2, 1, 0]

def sort_colors(arr):
    a_pointer = 0
    b_pointer = len(arr) - 1
    c_pointer = 0

    while c_pointer <= b_pointer:
        print('check loop_top:::', 'arr:', arr, '/', 'c_pointer:', c_pointer)
        if arr[c_pointer] == 0:
            arr[a_pointer], arr[c_pointer] = arr[c_pointer], arr[a_pointer]
            a_pointer += 1
            c_pointer += 1
        elif arr[c_pointer] == 2:
            arr[c_pointer], arr[b_pointer] = arr[b_pointer], arr[c_pointer]
            b_pointer -= 1
        else: # arr[c_pointer] == 1
            c_pointer += 1
        print('check loop_bot:::', 'arr:', arr, '/', 'c_pointer:', c_pointer)

print(sort_colors(nums))
print(f'result: {nums}')

---

출처: 코드없는 프로그래밍