퀵정렬과 병합정렬(Quick Sort and Merge Sort)

퀵정렬과 병합정렬(Quick Sort and Merge Sort)

🔍 자세히보기 : 퀵정렬(퀵소트)과 병합정렬은 많이 활용되고 비교되는 것이다.

• 퀵 정렬의 시간복잡도는 최악의 경우 O(n²)이며 평균의 경우 O(nlogn)이다.
  • 최악: 피벗에 의한 원소들의 부분집합이 1개와 n-1개로 분할되는 경우가 반복되는 경우
• 병합 정렬은 성능의 저하 없이 항상 O(nlogn)이다.
• 퀵 정렬은 불안전 정렬이고, 병합 정렬은 안정 정렬이다.
  • 동일한 값에 대해 기존의 순서가 유지되는 것이 안정 정렬이다.
• 퀵 정렬이 사용 되는 이유
  • 퀵 정렬은 피벗이라는 별도의 노드를 지정해두고 재귀적으로 수행을 하기 때문에 통상적으로 병합정렬보다 더 빠르다.
  • 병합 정렬은 전체 데이터를 기준으로 처음과 끝을 계속해서 탐색하기 때문에 퀵소트에 비해 느리다.
  • 한정적인 범위에서 데이터를 정렬하기 때문에 캐시를 덜 활용하고, 하드웨어적으로 효율적이다.
• 병합 정렬이 활용되는 이유
  • 퀵 정렬보다 빠르지는 않지만, 안정(stable) 정렬이기 때문에 데이터가 중복되었더라도 영향을 덜 받기 때문이다.
  • 퀵 정렬은 성능이 우수함에도 성능 편차가 크고, 피벗(노드) 설정 등의 다루기 어려운 점이 존재하기 때문에 실무에서는 활용되기가 어렵다.

[Quick sort] vs [Merge sort]

퀵정렬(Quick Sort)

1. 퀵소트의 최선의 경우

2. 퀵소트의 최악의 경우

• 퀵정렬은 불안정 정렬의 대표적인 경우로서, 노드의 값이 중복되는 경우에는 계속해서 swap(교환)을 시도한다.
• 퀵정렬은 최악의 경우에 첫번째 노드를 피벗으로 설정하고 불균형하게 분할정복을 시도하여 성능이 안 좋아진다.
  • 속도는 알고리즘을 처리하고 결과를 도출하는 속도(주로 소프트웨어에 영향을 주고 받음)
  • 성능은 메모리에 영향을 주는 정도(주로 하드웨어에 영향을 주고 받음)

# 퀵소트 파이썬 코드 case - 1 : 전체코드
def quick_sort(node, first, last):
    def partition(first,last):
        pivot = node[last]
        left = first
        # print(pivot, first,last)    # 확인용

        for right in range(first, last):
            if node[right] < pivot:
                node[left], node[right] = node[right], node[left]
                left += 1
        node[left], node[last] = node[last], node[left]

        return left

    # 첫번째 노드가 마지막 노드보다 작은 경우, 재귀진행
    if first < last:
        pivot = partition(first, last)
        quick_sort(node, first, pivot - 1)
        quick_sort(node, pivot + 1, last)

node = [54, 26, 93, 17, 77, 31, 44, 55, 20]
quick_sort(node, 0, 8)
print(node)

# 퀵소트 파이썬 코드 case - 2 : 전체코드
def quick_sort(ARRAY):
    ARRAY_LENGTH = len(ARRAY)
    if ARRAY_LENGTH <= 1:
        return ARRAY
    else:
        PIVOT = ARRAY[0]
        GREATER = [element for element in ARRAY[1:] if element > PIVOT]
        LESSER = [element for element in ARRAY[1:] if element <= PIVOT]
        return quick_sort(LESSER) + [PIVOT] + quick_sort(GREATER)

ARRAY = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(quick_sort(ARRAY))

병합정렬(Merge Sort)

• 병합정렬 알고리즘을 구현하는 접근 방식은 두 부분으로 나뉩니다.
• 첫 번째 부분은 분할정복 방법의 분할 구성 요소를 수행합니다.
  • 첫 번째 부분에서의 주요 코드구현은 초기 리스트를 더 작은 구성 요소로 나눕니다.
  • 초기 리스트 분할은 분리된 각 구성 요소를 더 이상 분할할 수 없는 경우에만 중지됩니다.

def test_recur_divide(list):
    # 1. 리스트의 길이를 저장합니다.
    list_length = len(list)

    # 2. 리스트의 길이가 1이 될때까지, 즉 분할할 수 없을 때까지 아래 로직을 반복 수행합니다.
    if list_length == 1:
        return list

    # 3. 리스트의 중간 지점을 식별하고 리스트를 left_partition과 right_partition으로 분할합니다.
    mid_point = list_length // 2

    # 4. 모든 파티션이 분할할 수 없는 작은 구성 요소로 분할되도록 하려면,
    # 아래처럼 test_recur_divide 함수가 재귀적으로 호출됩니다.
    # test_recur_divide 함수 안에 매개변수는 두가지로 나뉘어서 전달됩니다.

    # left_partition은 리스트의 0번째 인덱스부터 중간지점 인덱스까지의 값을 전달받고,
    # right_partition은 리스트의 (중간지점+1)번째 인덱스부터 마지막지점 인덱스까지의 값을 전달받습니다.
    left_partition = test_recur_divide(list[:mid_point])
    right_partition = test_recur_divide(list[mid_point:])

    # 5. test_recur_divide 함수는 정렬된 왼쪽과 오른쪽 파티션으로 구성된 리스트를 반환합니다.
    return test_sort_combine(left_partition, right_partition)

• 병합 정렬 알고리즘의 두 번째 부분은 전달받은 리스트 내의 요소를 지정된 순서로 정렬하는 작업입니다.
• 아래 예시에서 보여지는 알고리즘의 정렬 순서는 오름차순으로 진행됩니다.

# 6. 두 개의 리스트를 받아 두 리스트 내의 요소로 정렬된 리스트를 반환합니다.
def test_sort_combine(left, right):
    # 7. 정렬된 결과값으로 채워질 비어있는 리스트변수 output을 초기화합니다.
    # 리스트를 반복할 때 사용되는 두 개의 변수 i와 j를 초기화합니다.
    output = []
    i = j = 0

    # 8. 두 변수 i와 j가 왼쪽과 오른쪽 리스트의 길이보다 작으면 while 루프를 실행합니다.
    while i < len(left) and j < len(right):
        # 9. 각 반복 동안 두 리스트의 모든 위치에 있는 요소를 비교합니다.
        if left[i] < right[j]:
            # 오름차순으로 정렬하기위해 output변수에는 더 작은 값으로 채워집니다.
            output.append(left[i])
            # 10. 변수 i값을 +1 함으로써 오른쪽으로 한칸 이동시킵니다.
            i += 1
        else:
            output.append(right[j])
            j += 1
    # 11. 남아있는 리스트 요소에서 현재 i, j 값을 기준으로 각각 리스트의 마지막지점 인덱스까지 값을 넣고 결과값을 반환합니다.
    output.extend(left[i:])
    output.extend(right[j:])

    return output

def test_result():
    unsorted_list = [2, 6, 8, 2, 3, 9, 1, 4, 9]
    print(unsorted_list)
    sorted_list = test_recur_divide(unsorted_list)
    print(sorted_list)

test_result()

• sorted_list 변수는 test_recur_divide 함수의 결과를 반환합니다.