TIL #13 : 퀵 정렬, 병합 정렬, 이진 탐색

📝 퀵 정렬

기준점(pivot)을 정해, 주어진 배열에서 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모은다. 그리고 모인 왼쪽, 오른쪽의 부분 배열에 대해 재귀용법을 사용해 같은 작업을 반복하는 방식

def quick_sort(data):
    if len(data) <= 1:
        return data
    
    pivot = data[0]
    left,right = [], []

    for num in data[1:]:
        if num > pivot:
            right.append(num)
        else:
            left.append(num)

    return quick_sort(left)+[pivot]+quick_sort(right)

👏 시간 복잡도

최선	평균	최악
O(n*log(n))	O(n*log(n))	O(n^2)

📝 병합 정렬

하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방식

• 두 개의 함수로 구현 가능
  • mergeSplit : 리스트 분할
  • merge : 리스트 병합

def mergeSplit(data):
    if len(data) <= 1:
        return data

    mid = len(data) // 2
    left = mergeSplit(data[:mid])
    right = mergeSplit(data[mid:])

    return merge(left, right)

def merge(left, right):
    merged = list()

    while left and right:
        if left[0] < right[0]:
            merged.append(left.pop(0))
        else:
            merged.append(right.pop(0))

    while left:
        merged.append(left.pop(0))

    while right:
        merged.append(right.pop(0))

    return merged

👏 시간 복잡도

최선	평균	최악
O(n*log(n))	O(n*log(n))	O(n*log(n))

📝 이진 탐색 (Binary Search)

탐색할 자료를 반으로 나누어 탐색 범위를 좁혀가며 해당 데이터가 있을만한 곳을 탐색하는 방법
❗ 이진 탐색은 데이터가 이미 정렬되어있는 상태에서 진행 ❗

def binarySearch(data, search_data):
    if len(data) == 0:
        return False
    if len(data) == 1:
        if search_data == data[0]:
            return True
        else:
            return False

    mid = len(data)//2
    if search_data == data[mid]:
        return True
    else:
        if search_data < data[mid]:
            return binarySearch(data[:mid], search_data)
        else:
            return binarySearch(data[mid+1:], search_data)

👏 시간 복잡도

최선	평균	최악
O(log(n))	O(log(n))	O(n)