이 글은 정렬 (Sorting)에서 이어집니다.
다양한 정렬 방법의 특징이 궁금하시다면 위 링크를 참고해 주세요.

안녕하세요. 소리입니다 👋
이번 글에서는 퀵 정렬과 합병 정렬, 힙 정렬을 파이썬과 러스트로 구현해볼게요.

퀵 정렬

두 구현 모두 피벗을 배열의 가장 왼쪽 요소로 고르도록 구현했어요.
이 경우 이미 역순 정렬된 배열과 같은 불균형한 데이터가 들어올 때 $O(N^2)$의 시간이 걸릴 수 있습니다.

만약 아래 코드를 피벗을 임의값으로 선정하도록 수정한다면, 모든 데이터에 대해 평균 $O(NlogN)$ 시간으로 성능을 개선할 수 있어요.

Python

def quick_sort(array, start, end):  
    # 재귀 탈출  
    if end - start < 2:  
        return  
          
    pivot = start
    left, right = start + 1, end - 1  
    
    # 피벗 값을 기준으로 분할  
    while left <= right:  
    
        # 왼쪽에서부터 피벗보다 큰 요소 찾기  
        while left < end and array[left] <= array[pivot]:  
            left += 1  
            
        # 오른쪽에서부터 피벗보다 작은 요소 찾기  
        while right > pivot and array[right] >= array[pivot]:  
            right -= 1  
            
        # 각각 찾은 요소 교환  
        if left < right:  
            array[left], array[right] = array[right], array[left]  
              
    # 피벗을 나눈 배열 가운데로 이동  
    array[pivot], array[right] = array[right], array[pivot]  
    
    # 나눠진 배열 재귀적으로 정렬  
    quick_sort(array, start, right)  
    quick_sort(array, right + 1, end)

Rust

fn quick_sort<T: Ord>(array: &mut [T]) {
	let len = array.len();
	
	// 재귀 탈출
	if len < 2 {
		return;
	}
	
	let pivot = 0;
	let mut left = 1;
	let mut right = len - 1;
	
	// 피벗 값을 기준으로 분할
	while left <= right {
	
		// 왼쪽에서부터 피벗보다 큰 요소 찾기
		while left < len && array[left] <= array[pivot] {
			left += 1;
		}
		
		// 오른쪽에서부터 피벗보다 작은 요소 찾기
		while right > pivot && array[right] >= array[pivot] {
			right -= 1;
		}
		
		// 각각 찾은 요소 교환
		if left < right {
			array.swap(left, right);
		}
	}
	
	// 피벗을 나눈 배열 가운데로 이동
	array.swap(pivot, right);
	
	// 나눠진 배열 재귀적으로 정렬
	quick_sort(&mut array[..right]);  
	quick_sort(&mut array[(right + 1)..]);
}

합병 정렬

합병 정렬을 구현할 때는 배열을 합치는 부분에 주의해야 해요.
배열을 합칠 때, 비교하는 두 요소가 같은 값을 가진다면 앞선 위치에 있던 요소를 먼저 선택하도록 구현해야 합니다.
그렇게 하지 않으면 합병 정렬의 가장 큰 특징인 안정성이 사라지기 때문이에요.

Python

def merge_sort(array, start, end):  
    # 재귀 탈출  
    if end - start < 2:  
        return  
        
    mid = (start + end) >> 1  
    
    # 배열을 반으로 나눈 후 각각 재귀적으로 정렬  
    merge_sort(array, start, mid)  
    merge_sort(array, mid, end)  
    
    merged = []  
    left, right = start, mid  
    
    # 배열 합치기  
    while left < mid and right < end:  
        if array[left] <= array[right]:  
            merged.append(array[left])  
            left += 1  
        else:  
            merged.append(array[right])  
            right += 1  
    merged.extend(array[left:mid]) 
	merged.extend(array[right:end])
        
    # 원래 배열에 합친 결과 넣기  
    for idx in range(end - start):  
        array[idx + start] = merged[idx]

Rust

fn merge_sort<T: Ord + Copy>(array: &mut [T]) {  
    let len = array.len();  
    
	// 재귀 탈출
    if len < 2 {  
        return;  
    }  
    
    let mid = len >> 1;  
    
    // 배열을 반으로 나눈 후 각각 재귀적으로 정렬  
    merge_sort(&mut array[0..mid]);  
    merge_sort(&mut array[mid..len]);  
    
    let mut merged = Vec::with_capacity(len);  
    
    let mut left = 0;  
    let mut right = mid;  
    
    // 부분 배열 합치기  
    while left < mid && right < len {  
        if array[left] <= array[right] {  
            merged.push(array[left]);  
            left += 1;  
        }  
        else {  
            merged.push(array[right]);  
            right += 1;  
        }  
    }  
    merged.extend(&array[left..mid]);  
	merged.extend(&array[right..len]);
    
    // 원래 배열에 합친 결과 넣기   
	array.copy_from_slice(&merged);  
}

힙 정렬

두 구현 모두 힙을 구성할 때 하향식(Top-down) 방법을 사용했어요.
지난 글에서는 설명을 상향식(Bottom-up) 방법으로 진행했지만, 실제로 속도에 이점이 있는 방법은 하향식이기 때문이에요.

Bottom-up과 Top-down 방법의 차이

힙에 요소를 추가할 때, 상향식 방법은 요소를 아래에서부터 위 노드로 올려요.
반대로 하향식 방법은 요소를 위에서부터 아래로 내려요.

힙에 하나의 요소를 추가할 때는 상향식 방법이 좋아요.
두 방법 모두 $O(logN)$의 시간이 걸리지만, 상향식 방법이 요소를 추가하는 동작이 더 간단하기 때문입니다.

그러나 배열 전체를 힙 구조로 만들 때는 하향식 방법이 유리해요.
상향식은 $O(NlogN)$의 시간이 걸리지만, 하향식 방법은 $O(N)$에 수렴하는 시간이 걸리기 때문이에요.
하향식 방법을 사용하면 리프 노드에 들어가는 계산을 줄여 전체적인 시간을 크게 감소시켜요.

Python

def heap_sort(array):  
    # top-down 동작을 함수로 정의  
    def sift_down(array, root, size):  
        parent = root  
        child = root << 1 | 1  
        
        # 아래로 내려가며 힙 구조 속성을 만족하도록 교환 작업 진행  
        while child < size:  
            # 왼쪽 노드와 오른쪽 노드 중 큰 값 선택  
            if child + 1 != size and array[child] < array[child + 1]:  
                child += 1  
                
            # 부모가 선택된 자녀보다 작다면 교환  
            if array[parent] < array[child]:  
                array[parent], array[child] = array[child], array[parent]  
                parent = child  
            else:  
                break  
            child = parent << 1 | 1  
            
    # 배열을 최대 힙 구조로 만듦  
    size = len(array)  
    for i in range(size // 2 - 1, -1, -1):  
        sift_down(array, i, size)  
        
    # 힙에서 하나씩 꺼내 정렬을 시작  
    for i in range(size - 1, 0, -1):  
        array[0], array[i] = array[i], array[0]  
        sift_down(array, 0, i)

Rust

fn heap_sort<T: Ord>(array: &mut [T]) {  
    // top-down 동작을 함수로 정의  
    fn sift_down<T: Ord>(array: &mut [T], root: usize) {  
        let len = array.len();  
        let mut parent = root;  
        let mut child = root << 1 | 1;  
          
        // 아래로 내려가며 힙 구조 속성을 만족하도록 교환 작업 진행  
        while child < len {  
            // 왼쪽 노드와 오른쪽 노드 중 큰 값 선택  
            if child + 1 != len && array[child] < array[child + 1] {  
                child += 1;  
            }  
              
            // 부모가 선택된 자녀보다 작다면 교환  
            if array[parent] < array[child] {  
                array.swap(parent, child);  
                parent = child;  
            }  
            else {  
                break;  
            }  
            child = parent << 1 | 1;  
        }  
    }  
      
    // 배열을 최대 힙 구조로 만듦  
    let len = array.len();  
    for i in (0..len / 2).rev() {  
        sift_down(array, i);  
    }  
      
    // 힙에서 하나씩 꺼내 정렬을 시작 
    for i in (1..len).rev() {  
        array.swap(0, i);  
        sift_down(&mut array[..i], 0);  
    }  
}