[자료구조] 퀵정렬 VS 병합정렬

퀵 정렬

분할 정복 (Devide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘

기준값(Pivot)을 중심으로 자료를 왼쪽 부분집합과 오른쪽 부분집합으로 분할한다. 왼쪽 부분집합으로 기준값보다 작은 원소를 이동시키고, 오른쪽 부분집합으로 기준값보다 큰 원소를 이동시킨다. 퀵 정렬은 분할과 정복(Divide and Conquer)라는 작업을 반복하여 수행한다.

 

 

특징

 

• 기본적으로 지원되는  내장 정렬 함수는 대부분은 퀵 정렬을 기본으로 한다.
• 성능은 pivot 값을 어떻게 선택하느냐에 따라 크게 달라질 수 있음.
• 시간 복잡도: 최선의 경우 O(NlogN), 최악의 경우 O(N^2)

 

활용 케이스

 

• 메모리가 부족하고(병합정렬 사용 불가)할 경우
• 배열이 이미 정렬/역정렬되어있을 가능성이 없고(퀵소트 최악의 경우)
• 동일한 요소의 자리가 바뀌어도 상관 없는 경우(not stable하므로)

퀵 정렬의 최악의 경우는, 기준 원소가 항상 유일한 최소 원소이거나 최대 원소일 경우이다. 즉, 정렬 또는 역순정렬되어있을 경우 정렬이 n-1번 수행되면서 최악의 경우가 발생한다. 

 

하지만 참조 지역성 관점에서 퀵정렬이 병합정렬보다 빠르다. (배열인 경우 더욱 효과적)

자주 사용되는 Page는 물리 메모리에만이 아니라 캐시에도 두는데, 지역성의 원리에 따라 Hit율이 높다면 캐시에 해당 Page를 자주 접근하게 되어 훨씬 성능이 올라가게 되는 것이다.

이 지역성의 원리에 따라, 퀵 정렬은 병합 정렬 대비 더 빠르게 주변 데이터에 접근하므로 속도가 일반적으로 더 빠르다.

 

# 파이썬 퀵정렬 구현
def qsort(data):
    if len(data) <= 1:
        return data
    
    pivot,tail = data[0], data[1:]

    left = [ x for item in tail if pivot > x ]
    right = [ x for item in tail if pivot <= x ]
    
    return qsort(left) + [pivot] + qsort(right)

 

병합정렬

퀵 정렬과 마찬가지로 분할 정복 방법을 통해 정렬이다. 퀵 정렬과 비슷하지만 안정 정렬(stable sort)이다.

 

특징

 

• 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
• 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
• 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.
• 메모리 소모량이 큰 편이다.
• 시간 복잡도: O(NlogN)

 

활용케이스

 

• 배열이 이미 정렬되어있을 가능성이 있으며, 메모리가 충분한 경우
• 병합 정렬은 순차적인 비교를 통해 정렬하므로, LinkedList의 정렬에 효율적이다.
• 병합정렬은 추가 메모리를 요구하므로, 메모리 효율이 중요한 경우 퀵정렬이 낫다.

 

이것을 파이썬 코드로 구현을 해보면, 우선 분할 함수와 머지 함수로 나눠서 구현할 수 있다.

 

# 분할힘수
def split_func(data):
    medium = int(len(data) / 2)
    print (medium)
    left = data[:medium]
    right = data[medium:]
    print (left, right)

# 머지함수
def merge(left, right):
    merged = list()
    left_point, right_point = 0, 0 #인덱스번호
    
    # case1 - left/right 둘다 있을때(데이터가 있을때)
    while len(left) > left_point and len(right) > right_point:
        if left[left_point] > right[right_point]:
            merged.append(right[right_point])
            right_point += 1
        else:
            merged.append(left[left_point])
            left_point += 1

    # case2 - left 데이터가 없을 때
    while len(left) > left_point:
        merged.append(left[left_point])
        left_point += 1
        
    # case3 - right 데이터가 없을 때
    while len(right) > right_point:
        merged.append(right[right_point])
        right_point += 1
    
    return merged

이 두 부분을 합치면, 최종적으로 이런 코드로 구현할 수 있다.

# 최종코드

def merge(left, right):
    merged = list()
    left_point, right_point = 0, 0 #인덱스번호
    
    # case1 - left/right 둘다 있을때(데이터가 있을때)
    while len(left) > left_point and len(right) > right_point:
        if left[left_point] > right[right_point]:
            merged.append(right[right_point])
            right_point += 1
        else:
            merged.append(left[left_point])
            left_point += 1

    # case2 - left 데이터가 없을 때
    while len(left) > left_point:
        merged.append(left[left_point])
        left_point += 1
        
    # case3 - right 데이터가 없을 때
    while len(right) > right_point:
        merged.append(right[right_point])
        right_point += 1
    
    return merged

 

 

퀵정렬 VS 병합 정렬 비교

구분	퀵 정렬	병합 정렬
부분 배열의 구획	나뉘어진 배열은 여러 비율로 나뉜다.	배열은 항상 반으로 나뉜다.
최악의 경우 시간복잡도	O(n^2)	O(nlogn)
사용 용도	작은 크기의 배열에서 잘 동작	어떤 크기의 Dataset에서도 적절히 동작
효율성	작은 크기 Dataset에서는 병합 정렬보다 빠르다.	큰 Dataset에서는 퀵 정렬보다 빠르다.
정렬 방식	내부 정렬	외부 정렬
별도 저장 공간	불 필요	필요
참조 지역성	좋음	퀵 정렬 대비 나쁨
Stable	X(그러나 구현 방식에 따라 가능)	O