정렬 알고리즘 (3) : 합병 정렬, 퀵 정렬

지난 시간에 이어 이번 글에서도 정렬 알고리즘에 대해 이어 설명하겠습니다.

이번 글에서는 합병 정렬과 퀵 정렬에 대해 소개하겠습니다. 

---

합병 정렬 Merge Sort

• 합병 정렬의 개념

합병 정렬은 분할 정복 (Divide and Conquer) 방식으로 큰 문제를 반으로 쪼개가며 작은 문제로 만든 후, 작은 문제를 해결한 결과를 합쳐 전체를 정렬하는 방식의 알고리즘 입니다. 

여기서 등장하는 분할 정복이라는 개념을 아주 중요한 개념이기 때문에 다음 번에 하나의 큰 주제로 자세히 설명하도록 하겠습니다.

 

• 합병 정렬의 기본 로직 

합병 정렬은 크게 분할과 합병 과정으로 이루어집니다. 

• 분할 Divide

1. 현재 배열의 ( 시작 인덱스 + 종료 인덱스 ) / 2 한 값을 기준으로 현재 배열을 받으로 쪼갠다.
2. 쪼갠 배열의 크기가 1보다 작거나 같을 때까지 분할 작업을 반복한다.

• 합병 Merge

1. 쪼갠 배열 A의 현재 인덱스를 i로, B의 현재 인덱스를 j로 설정하고, 각 변수에 각 배열의 시작 인덱스 값을 저장한다.
2. A[i] 와 B[j]를 비교하여 작은 값을 새로운 배열 C에 저장한다.
3. C 배열에 값을 저장한 배열의 인덱스는 1을 증가시켜 다음 원소를 비교 대상으로 설정한다.
4. 1~3 과정을 i 또는 j가 각자 배열의 종료 위치에 도달할 때까지 반복 수행한다.
5. A 또는 B 배열 중 종료 위치에 도달하지 못한 배열의 값을 순서대로 전부 C 배열에 저장한다.
6. C 배열을 원래 배열에 저장시킨다. 

• 합병 정렬의 복잡도 

합병 과정은 하나의 배열을 쪼갠 두 개의 배열을 정렬하기 때문에 각 쪼개진 배열의 크기만큼 시간이 걸리는데 결국 두 배열의 합인,  배초기 배열의 전체 길이만큼의 시간이 걸립니다. 즉,  합병 과정의 시간 복잡도는 O(n)입니다.

분할 과정은 크기 n인 배열을 분할하면 n/2*2이고, 그 다음 분할은 n/4*4로 매 분할마다 반으로 감소합니다. 따라서 분할 과정의 시간 복잡도는 O(log n)입니다.

결론적으로 두 과정을 모두 수행해야 하는 합병 정렬의 시간 복잡도는 O(nlogn)이 됩니다. 

제가 위에서 설명한 방식은 C 라는 새로운 배열을 추가하여 정렬을 했습니다. 따라서 공간 복잡도는 기존 배열 크기의 또 다른 배열(c)가 존재해야 하기 때문에 O(2n)입니다.  

삽입 정렬 역시 in-place 알고리즘 이기 때문에 공간 복잡도가 O(n)입니다. 

• 합병 정렬 Python3 구현 코드 

def merge_sort(q):
		# 쪼개진 배열의 크기가 1이 될 때까지 쪼개기
    if len(q) <= 1:
        return q       
    M = len(q)//2
    A = merge_sort(q[:M])
    B = merge_sort(q[M:])
		# 쪼갠 배열 2개를 합병하며 정렬하기 
    return merge(A,B)

def merge(A,B):
		# 정렬된 배열을 저장할 보조 배열 C
    C = []
    i = j = 0

    while len(A) > i and len(B) > j:
        if A[i] > B[j]:
            C.append(B[j])
            j += 1
        else:
            C.append(A[i])
            i += 1
    
    while len(A) > i and len(B) <= j:
        C.append(A[i])
        i += 1
    
    while len(B) > j and len(A) <= i:
        C.append(B[j])
        j += 1
    
    return C

---

퀵 정렬 Quick Sort

• 퀵 정렬의 개념

퀵 정렬 또한 위에서 설명한 분할 정복 방식을 사용합니다. pivot이라고 하는 기준값을 설정하여 이를 기준으로 작은 값을 왼쪽으로, 큰 값은 오른쪽으로 옮기는 방식으로 정렬하는 알고리즘입니다. 합병 정렬과 마찬가지로 분할된 배열의 크기가 1이 되면 배열이 모두 정렬된 것입니다. 

• 퀵 정렬의 기본 로직

1. 배열의 요소 중 하나를 pivot으로 선정한다. (보통 배열의 가운데 값으로 선정합니다.)
2. pivot을 기준으로 pivot보다 작은 요소들은 모두 pivot 왼쪽으로, 큰 요소들은 모두 오른쪽으로 옮깁니다. 그 결과 배열의 상태는 [pivot 보다 작은 원소들 - pivot -pivot보다 큰 원소들]로 됩니다.
3. pivot을 제외한 왼쪽 배열과 오른쪽 배열을 순환 호출을 이용하여 위 과정을 반복하여 정렬합니다.
4. 순화 호출된 왼쪽, 오른쪽 배열들도 각 리스트에서 다시 pivot을 선정하고, 그것을 기준으로 pivot보다 작은 요소, 큰 요소를 각각의 리스트로 분할합니다.
5. 분할된 리스트의 크기가 0또는 1이 될 때까지 반복합니다.

• pivot을 기준으로 값들을 정렬하는 1회전 마다 최소 하나의 원소 (pivot)의 위치가 정해지기 때문에 반복이 반드시 종료함을 알 수 있습니다.

• 퀵 정렬의 복잡도

퀵 정렬은 분할과 동시에 정렬을 수행합니다. 각 정렬은 배열의 크기 n만큼 비교를 하며 이를 통 분할 깊이인 log n 만큼 수행하기 때문에 총 비교 횟수는 nlogn으로 시간 복잡도는 O(nlogn)입니다. 그러나 이미 정렬되어 있는 배열의 경우 최악의 경우로 분할이 n 만큼 일어나기 때문에 시간 복잡도가 O(n^2)이 되기도 합니다. 이를 방지하기 위해 전체 배열 값 중 중간값이나 랜덤 값으로 pivot을 선정하는 것이 중요합니다. 

• 퀵 정렬 Pyhton3 구현 코드 

def quick_sort(q):
    if len(q) <= 1:
        return q
    # 중간값을 pivot으로 선정
    pivot = q[len(q)//2]
    left, mid, right = [], [], []
    for i in q:
				# pivot보다 작으면 왼쪽 리스트에
        if i < pivot:
            left.append(i)
				# pivot보다 크면 오른쪽 리스트에
        elif i > pivot:
            right.append(i)
				# pivot과 같으면 그대로 pivot과 같은 위치에 
        else:
            mid.append(i)
		# 분할된 왼쪽, 오른쪽 리스트를 대상으로 다시 quick_sort
		# 가운데에 pivot이 위치
    return quick_sort(left) + mid + quick_sort(right)

---

이번 글에서는 정렬 알고리즘과 그 중 합병 정렬과 퀵 정렬에 대해 설명하였습니다.

마지막으로 시간 복잡도를 참고할 수 있는 표를 보여드리고 글을 마치도록 하겠습니다.

감사합니다 :)

 

---

References

• gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

• shinsunyoung.tistory.com/13