접근
분할 정복의 접근 방식은 아래와 같다:
- 하나의 문제를 하나 이상의 그보다 작은 크기의 문제로 분할한다.
- 분할된 각각의 작은 문제를 해결한다.
- (필요할 경우) 각각의 작은 문제에서 도출된 답을 합친다.
병합 정렬에 이상의 접근 방식을 적용하면:
- 입력된 배열을 2개의 부분 배열로 분할한다.
- 양 쪽의 배열을 각각 정렬한다.
- 정렬된 양 배열을 합친다.
이를 바탕으로 간단하게 의사 코드를 작성하면:
병합 정렬(배열) {
만약 배열 길이가 2보다 작을 경우 {
(길이가 1인 배열은 사실상 정렬된 상태이므로) 입력된 배열을 그대로 반환
} 그렇지 않을 경우 {
좌측 배열에 0부터 mid까지를 복사
우측 배열에 mid + 1부터 배열의 끝까지를 복사
병합 정렬(좌측 배열)
병합 정렬(우측 배열)
좌측 배열과 우측 배열을 합친 결과물을 반환
}
}Rust 코드
재귀 (Recursion)
정렬 함수
fn mergesort(vec: &Vec<i32>) -> Vec<i32> {
if vec.len() < 2 {
// 배열 크기가 1이면, 그대로 반환
// 입력은 &Vec<i32>로 받았는데 반환형이 참조 변수가 아니므로,
// to_vec() 메소드를 통해 &Vec<i32>를 Vec<i32>로 변환해서 반환한다
vec.to_vec()
} else {
// 배열 크기가 2 이상일 경우
// 배열을 2개로 나누고 각각 정렬 후 병합해서 반환
let mid = vec.len() / 2;
let left = mergesort(&vec[0..mid].to_vec());
let right = mergesort(&vec[mid..].to_vec());
merge(&left, &right)
}
}병합 함수
fn merge(left: &Vec<i32>, right: &Vec<i32>) -> Vec<i32> {
let mut temp: Vec<i32> = Vec::new();
let mut left_counter = 0;
let mut right_counter = 0;
// 배열의 첫 번째 원소를 비교해가며, 작은 숫자부터 반환할 벡터에 집어넣음
while left_counter < left.len() && right_counter < right.len() {
if left[left_counter] < right[right_counter] {
temp.push(left[left_counter]);
left_counter += 1;
} else {
temp.push(right[right_counter]);
right_counter += 1;
}
}
// 좌측 배열에만 숫자가 남아있을 경우
if left_counter < left.len() {
while left_counter < left.len() {
temp.push(left[left_counter]);
left_counter += 1;
}
}
// 우측 배열에만 숫자가 남아있을 경우
if right_counter < right.len() {
while right_counter < right.len() {
temp.push(right[right_counter]);
right_counter += 1;
}
}
// 병합된 배열을 반환
temp
}여담
- 코드 출처는 여기. 혼자 힘으로 해 보려고 했는데 Rust에 익숙하지 않아서 좀 무리였다. 거의 바꾼 건 없다.
+=연산자 정도? - 처음에는 배열을 쓰려고 했는데, 배열은 첫 번째 원소를 Pop하기에는 부적절한 자료형이라는 걸 알고 벡터로 계획을 바꿨다. 근데 벡터도 후방에서의 Pop만 지원하고 전방에서는 불가능해서, 다음에는 데크로 바꿨다. 코드를 대충 쓰고 데크의 첫 번째 원소를 반환하는
first()메소드를 쓰려고 보니, 반환형이Option이더라. 아직Option을 다룰 줄 몰라서(예외 처리?를 할 줄 몰라서) 최종적으로 여기서 막혔다. 그래서 구글링으로 위 링크를 참고하게 됨... - 교수님은 재귀 말고도 DP 등의 다른 방법으로도 구현이 가능하다고 하셨었다. 다른 테크닉으로도 병합 정렬을 구현할 수 있게 되면, 나중에 이 글에 코드를 추가해야 겠다.
- Kotlin 배웠을 때 처럼, 일단 구글 보면서 몸으로 부딪히면 그 과정에서 익히는 게 분명 있을 거다. 배열의 슬라이싱이 그렇다. 처음은 항상 어려운 게 맞으니까 부족한 것 같아도 기 죽지 말자. 중간고사 보고 러스트 튜토리얼 조금 더 파 봐야겠다...
Python 코드
재귀 (Recursion)
정렬 함수
def mergesort_sort(arr: list) -> list:
if (len(arr) < 2):
return arr
else:
mid = len(arr) // 2
left = mergesort_sort(arr[0:mid])
right = mergesort_sort(arr[mid:])
return mergesort_merge(left, right)병합 함수
def mergesort_merge(arr1: list, arr2: list):
temp = []
while (len(arr1) and len(arr2)):
if (arr1[0] < arr2[0]): temp.append(arr1.pop(0))
else: temp.append(arr2.pop(0))
if (len(arr1)): temp.extend(arr1)
if (len(arr2)): temp.extend(arr2)
return temp
if __name__ == "__main__":
arr = [15, 22, 13, 27, 12, 10, 20, 25]
print(mergesort_sort(arr))
i meant to be