병합 정렬, 퀵 정렬

병합 정렬

병합 정렬은 분할 정복(divide and conquer) 알고리즘 중 하나로, 주어진 배열을 두 개의 작은 배열로 분할한 후, 각각을 정렬한 다음, 두 개의 정렬된 배열을 병합하여 전체 배열을 정렬하는 알고리즘이다.

• 만약 배열의 길이가 1 이하이면, 이미 정렬된 것으로 간주하고, 배열을 반환한다.
• 배열을 두 개의 작은 배열로 분할한다.
• 분할된 두 배열을 각각 병합 정렬을 호출하여 정렬한다.
• 두 정렬된 배열을 병합한다.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    # 배열을 두 개의 작은 배열로 분할
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    # 분할된 두 배열을 각각 병합 정렬을 호출하여 정렬
    left = merge_sort(left)
    right = merge_sort(right)

    # 두 정렬된 배열을 병합합니다.
    return merge(left, right)


def merge(left, right):
    result = []

    # 두 배열의 첫 번째 원소를 비교하여 작은 원소를 결과 배열에 추가
    while len(left) > 0 and len(right) > 0:
        if left[0] < right[0]:
            result.append(left[0])
            left = left[1:]
        else:
            result.append(right[0])
            right = right[1:]

    # 남은 원소들을 결과 배열에 추가
    if len(left) > 0:
        result.extend(left)
    if len(right) > 0:
        result.extend(right)

    return result
    
arr = [5, 2, 9, 1, 5, 6, 3]
sorted_arr = merge_sort(arr)
print(sorted_arr)

# [1, 2, 3, 5, 5, 6, 9]

연습 문제

1부터 100까지의 난수 10개를 생성하고, 다음의 요구 사항을 만족하는 모듈을 만들어보자.

import random

def merge_sort(arr, reverse=False):
    if len(arr) <= 1:
        return arr

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

    left = merge_sort(left, reverse)
    right = merge_sort(right, reverse)

    return merge(left, right, reverse)


def merge(left, right, reverse):
    result = []

    while len(left) > 0 and len(right) > 0:
        if reverse:
            if left[0] > right[0]:
                result.append(left[0])
                left = left[1:]
            else:
                result.append(right[0])
                right = right[1:]
        else:
            if left[0] < right[0]:
                result.append(left[0])
                left = left[1:]
            else:
                result.append(right[0])
                right = right[1:]

    if len(left) > 0:
        result.extend(left)
    if len(right) > 0:
        result.extend(right)

    return result


if __name__ == '__main__':
    # 1부터 100까지의 난수 10개 생성
    arr = random.sample(range(1, 101), 10)

    # 오름차순 정렬
    sorted_arr = merge_sort(arr)
    print(f"오름차순 정렬 결과: {sorted_arr}")

    # 내림차순 정렬
    sorted_arr = merge_sort(arr, reverse=True)
    print(f"내림차순 정렬 결과: {sorted_arr}")
    
# 오름차순 정렬 결과: [2, 28, 33, 63, 64, 68, 74, 85, 94, 97]
# 내림차순 정렬 결과: [97, 94, 85, 74, 68, 64, 63, 33, 28, 2]

---

퀵 정렬

퀵 정렬은 분할 정복(divide and conquer) 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 알고리즘이다. 배열을 분할하고, 각 분할된 배열을 정렬하면서 전체 배열을 정렬하는 방식이다.

알고리즘 동작 방식

1. 배열에서 하나의 원소를 기준(pivot)으로 선택한다. (대개 첫번째 원소, 마지막 원소, 중간 원소 중 하나를 선택)
2. 선택한 pivot을 기준으로 작은 값은 pivot 왼쪽에, 큰 값은 pivot 오른쪽에 위치하도록 분할한다. 이 과정을 "파티션(partition)"이라고 한다.
3. 분할된 왼쪽 부분배열과 오른쪽 부분배열에 대해 재귀적으로 퀵 정렬을 수행한다.
4. 재귀적인 정렬이 완료되면, 왼쪽 배열과 오른쪽 배열을 합쳐 전체 배열을 정렬한다.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[0]
    left = []
    right = []

    for i in range(1, len(arr)):
        if arr[i] < pivot:
            left.append(arr[i])
        else:
            right.append(arr[i])

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


if __name__ == '__main__':
    arr = [7, 1, 3, 5, 6, 2, 8, 4]
    sorted_arr = quick_sort(arr)
    print(sorted_arr)

# [1, 2, 3, 4, 5, 6, 7, 8]

연습 문제

1부터 100까지의 난수 10개를 생성하고, 다음의 요구 사항을 만족하는 모듈을 만들어보자.

import random

def quick_sort(arr, reverse=False):
    """퀵정렬 알고리즘을 이용한 정렬"""
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        left = [x for x in arr[1:] if x <= pivot]
        right = [x for x in arr[1:] if x > pivot]
        if not reverse:
            return quick_sort(left) + [pivot] + quick_sort(right)
        else:
            return quick_sort(right, reverse=True) + [pivot] + quick_sort(left, reverse=True)

# 1부터 100까지의 난수 10개 생성
random_numbers = [random.randint(1, 100) for _ in range(10)]

# 오름차순 정렬
sorted_numbers = quick_sort(random_numbers)
print("오름차순 정렬 결과:", sorted_numbers)

# 내림차순 정렬
reverse_sorted_numbers = quick_sort(random_numbers, reverse=True)
print("내림차순 정렬 결과:", reverse_sorted_numbers)

# 오름차순 정렬 결과: [8, 22, 28, 43, 43, 44, 45, 65, 73, 91]
# 내림차순 정렬 결과: [91, 73, 65, 45, 44, 43, 43, 28, 22, 8]