[Udemy] JavaScript 알고리즘 & 자료구조 마스터클래스_Section 16

* 수업은 JS 기반이지만 Python으로 구현

Section 16

퀵 정렬: 소개

합병 정렬과 비슷하게 배열을 0개 혹은 1개로 나누어 정렬한다. 아무 단일 요소나 피벗 포인트로 고를 수 있다. 이후 피벗 포인트보다 작은 숫자는 왼쪽으로 옮기고, 큰 숫자는 오른쪽으로 옮긴다. 이후 한 배열이 끝나면 피봇 포인트의 왼쪽에 있는 배열에 다시 그 행위를 반복하고 종료되면 오른쪽으로 넘어가 다시 반복한다. 이때 중요한 점은, 배열 한 번을 확인한 이후에 피봇 포인트의 인덱스는 고정된다는 것이다.

피봇 helper: 소개

• 배열이 주어지면, 피봇 헬퍼 함수를 이용해 요소를 피벗으로 지정한다.
• 피벗보다 작은 값은 모두 왼쪽으로 이동하며 피벗보다 큰 값은 모두 오른쪽으로 이동한다.
• 피벗을 기준으로 왼쪽과 오른쪽 어느쪽을 먼저 수행하던 상관없다.
• 헬퍼가 새로운 배열을 만들지 않고 제자리에서 수행해야 한다는 것이다.
• 완성이 되면 헬퍼는 피벗의 인덱스를 반환한다.
• 피벗 고르기
  • 퀵 정렬을 빠르게 하기 위해서는 피봇을 고르는데에 달려있다.
  • 이상적으로는 데이터 정렬에서 중앙값을 골라 왼쪽과 오른쪽의 길이가 비슷하면 좋다.
  • 전략적으로는 첫 번째 요소, 마지막 요소, 아니면 중간, 무작위 요소를 선택한다.

피봇 helper: 구현

• 배열, 시작 인덱스, 끝 인덱스라는 세 개의 인수를 받는다. 기본값으로 시작인덱스는 0, 끝 인덱스는 배열 길이 - 1이다.
  • for문에서 range 함수를 활용하는 경우, 끝 인덱스는 활용되지 않으므로 끝 인덱스를 배열 길이 그대로 둔다.
• 배열 시작에서 피봇을 고른다. (실제로는 아무거나 골라도 되지만, 계속 첫 번째 요소를 고르는 버전으로 진행한다.)
• 현재 피봇 인덱스를 카운터 피봇 인덱스 변수로 저장하여 마지막에 피벗 바꿀 위치를 계속 확인한다.
• 배열 시작부터 끝까지 루프를 수행한다.
  • 만약 피봇이 현재 비교하는 요소보다 크다면, 카운터 피봇 인덱스 변수를 증가시킨 후 카운터 피봇 인덱스와 현재 비교하는 요소의 인덱스를 교환한다.
• 시작했던 피벗과 카운터 피봇 인덱스를 바꾼 다음 카운터 피봇 인덱스를 반환한다.

 

• 파이썬 함수에서 매개변수에 디폴트값을 활용할 때, 아직 선언되지 않은 변수를 활용하지 못한다. 이 블로그를 참고하여 작성했다.

# pivot helper

def pivot(arr, start = 0, end = None):

    # 함수의 매개변수는 만들지 않은것을 활용하는게 불가능해보임
    # 일단 공석으로 두고, 공석이라면 배열의 길이와 같다고 두기
    if end is None:
        end = len(arr)

    # 피봇은 배열에서 start번 째인것으로 둔다.
    pivot = arr[start]
    # 위치를 바꿀 때 활용하는 인덱스 값을 저장
    # 일단 피봇의 위치에서 시작하여 조건에 따라 추후 수정
    swapIdx = start

    # 이미 피봇인 start 다음 위치부터 배열 끝까지 활용
    for i in range(start + 1, end):
        # 만약 피봇값이 배열 요소보다 더 크다면
        if pivot > arr[i]:
            # swapIdx 값을 한 개 올리고
            # 현재 비교 요소와 swapIdx번째의 요소를 바꾸라
            # swapIdx번째 요소는 피봇값보다 큰 요소들 중 가장 첫 번째 요소이다.
            swapIdx += 1
            arr[i], arr[swapIdx] = arr[swapIdx], arr[i]
        # 함수 작동 확인 요소
        print('i', i, 'swapIdx', swapIdx, 'arr[i]', arr[i], 'pivot', pivot)
    # 모든 교환이 끝난 후 swapIdx번째 요소는
    # 피봇값보다 작은 요소 중 가장 오른쪽에 위치한 것이다
    # 배열의 피봇 시작 값과 swapIdx번째의 값을 교환한다.
    # 결과: 피봇보다 작은 값들 ~ 피봇 ~ 피봇보다 큰 값들
    arr[start], arr[swapIdx] = arr[swapIdx], arr[start]
    # 함수 작동 확인 요소
    print(arr)
    
    return swapIdx
    
pivot([2, 3, 5, -3, 8, 6, 0, -5])

퀵 정렬: 구현

• 배열을 입력하면, 첫 번째 항목을취해 위치를 파악한 이후 그보다 작은 항목은 모두 왼쪽에, 큰 항목은 모두 오른쪽에 두고 인덱스를 반환한다.
• 업데이트된 피벗 인덱스를 헬퍼가 반환하면, 피벗 헬퍼를 재귀적으로 왼쪽과 오른쪽에 호출한다.
• 하위배열에 2개 미만의 요소가 있을 때 base case가 수행된다.

# Quick Sort
def quick(arr, left = 0, right = None):

    # pivot helper
    def pivot(arr, start = 0, end = None):

        # 함수의 매개변수는 만들지 않은것을 활용하는게 불가능해보임
        # 일단 공석으로 두고, 공석이라면 배열의 길이와 같다고 두기
        if end is None:
            end = len(arr)

        # 피봇은 배열에서 start번 째인것으로 둔다.
        pivot = arr[start]
        # 위치를 바꿀 때 활용하는 인덱스 값을 저장
        # 일단 피봇의 위치에서 시작하여 조건에 따라 추후 수정
        swapIdx = start

        # 이미 피봇인 start 다음 위치부터 배열 끝까지 활용
        for i in range(start + 1, end):
            # 만약 피봇값이 배열 요소보다 더 크다면
            if pivot > arr[i]:
                # swapIdx 값을 한 개 올리고
                # 현재 비교 요소와 swapIdx번째의 요소를 바꾸라
                # swapIdx번째 요소는 피봇값보다 큰 요소들 중 가장 첫 번째 요소이다.
                swapIdx += 1
                arr[i], arr[swapIdx] = arr[swapIdx], arr[i]
            # 함수 작동 확인 요소
            print('i', i, 'swapIdx', swapIdx, 'arr[i]', arr[i], 'pivot', pivot)
        # 모든 교환이 끝난 후 swapIdx번째 요소는
        # 피봇값보다 작은 요소 중 가장 오른쪽에 위치한 것이다
        # 배열의 피봇 시작 값과 swapIdx번째의 값을 교환한다.
        # 결과: 피봇보다 작은 값들 ~ 피봇 ~ 피봇보다 큰 값들
        arr[start], arr[swapIdx] = arr[swapIdx], arr[start]
        # 함수 작동 확인 요소
        print('>', arr)

        return swapIdx

    # 일단 공석으로 두고, 공석이라면 배열의 길이로 두기
    if right is None:
        right = len(arr)

    if left < right:
        # 피봇 헬퍼 함수를 통해 피봇 인덱스를 구한다.
        pivotIdx = pivot(arr, left, right)
        
        # 함수 작동 확인 요소
        print('> pivotidx', pivotIdx)

        # 매번 다른 데이터를 이용해 함수를 호출하는 부분
        # left
        print('> quick({}, {}, {})'.format(arr, left, pivotIdx - 1))
        quick(arr, left, pivotIdx - 1)
        
        # right
        print('< quick({}, {}, {})'.format(arr, pivotIdx + 1, right))
        quick(arr, pivotIdx + 1, right)

    return arr

quick([2, 3, 5, -3, 8, 6, 0, -5])
quick([2, -2, -7, 5, -3, 8, 6, 0, -5])

퀵 정렬: 빅오 복잡도

• 시간복잡도
  • Best: O(n log n)
  • Average: O(n log n)
  • Worst: O(n^2)
    • 매번 제일 크거나 제일 작은 것을 고르면 비교하는 항목이 많아진다. 어느정도 정렬이 되어있는 경우에는 무작위로 항목을 고르거나 매번 중간에 있는 요소를 고르는 것이 좋다.
• 공간복잡도
  • O(log n)