분할 정복: 퀵 정렬

접근

"[문제 분할 - 분할된 문제 해결 - 부분해 병합]의 3단계로 이루어지는 분할 정복에서, 병합 과정을 빼고 정렬할 수 있을까?" 라는 물음으로부터 만들어진 알고리즘이란다.

병합 정렬에서는 배열을 병합하는 과정에 비교적 많은 코드가 필요했는데, 퀵 정렬에서는 병합 과정이 없어진 만큼 그 부하가 분할 과정에 집중된다.

대충 의사 코드는 아래와 같다:

퀵 정렬 (배열, 시작 인덱스, 끝 인덱스) {
	만약 시작 인덱스 < 끝 인덱스일 경우 {
    	피봇 인덱스를 선언, 0으로 초기화
        피봇을 기준으로 피봇보다 작은 배열, 피봇보다 큰 배열로 분할
        퀵 정렬 (배열, 시작 인덱스, 피봇 인덱스 - 1)
        퀵 정렬 (배열, 피봇 인덱스 + 1, 끝 인덱스)
    }
}

퀵 분배 (배열, 시작 인덱스, 끝 인덱스) -> 피봇 인덱스 반환 {
	배열의 시작 인덱스를 피봇으로 설정
    현재 탐색 인덱스를 시작 인덱스 + 1로 설정
    다음 교체 인덱스를 시작 인덱스 + 1로 설정
    
    // 첫 번째는 피봇이라서 두 번째부터 탐색을 진행함
    배열의 두 번째 인덱스부터 끝까지 반복 {
            만약 배열의 현재 탐색 인덱스에 위치한 값 < 피봇이면 {
                현재 탐색 인덱스와 다음 교체 인덱스끼리 값을 변경
                다음 교체 인덱스에 1을 더함
    		}
		현재 탐색 인덱스에 1을 더함
    }
	배열이 나누어졌으면, 피봇보다 작은 숫자들 뒤에 피봇을 재배치
    피봇 인덱스를 반환
}

---

Rust 코드

나중에 시간이 나면 추가해보도록 하겠다. 나는 시간 빌 게이츠가 아니기에...

---

Python 코드

재귀 (Recursion)

정렬 함수

def quicksort(arr: list, low: int, high: int):
    if (low < high):
        pivot_index = quicksort_partition(arr, low, high)
        quicksort(arr, low, pivot_index)
        quicksort(arr, pivot_index + 1, high)

분할 함수

def quicksort_partition(arr: list, low: int, high: int) -> int:
    def __swap(arr: list, a: int, b: int):
        temp = arr[a]
        arr[a] = arr[b]
        arr[b] = temp

    pivot = arr[low]
    current_index = low + 1
    to_fill_index = low + 1

    while (current_index < high):
        if (arr[current_index] < pivot):
            __swap(arr, current_index, to_fill_index)
            to_fill_index += 1
        current_index += 1
    
    arr.insert(to_fill_index - 1, arr.pop(low))
    return to_fill_index - 1