728x90
*** 면접에서 직접 구현해보라고 하는 구현 방법!! ***
[병합 정렬 - merge]
배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘
[1, 2, 3, 5] # 정렬된 배열 A
[4, 6, 7, 8] # 정렬된 배열 B
[] # 두 집합을 합칠 빈 배열 C
↓
1단계 : [1, 2, 3, 5]
↓
[4, 6, 7, 8]
1과 4를 비교
1 < 4 이므로 1을 C 에 넣음
C:[1]
↓
2단계 : [1, 2, 3, 5]
↓
[4, 6, 7, 8]
2와 4를 비교
2 < 4 이므로 2를 C 에 넣음
C:[1, 2]
↓
3단계 : [1, 2, 3, 5]
↓
[4, 6, 7, 8]
3과 4를 비교
3 < 4 이므로 3을 C 에 넣음
C:[1, 2, 3]
↓
3단계 : [1, 2, 3, 5]
↓
[4, 6, 7, 8]
5와 4를 비교
5 > 4 이므로 4을 C 에 넣음
C:[1, 2, 3, 4]
↓
3단계 : [1, 2, 3, 5]
↓
[4, 6, 7, 8]
5와 6을 비교
5 < 6 이므로 5을 C 에 넣음
C:[1, 2, 3, 4, 5]
A 의 모든 원소는 끝
B에서 안 들어간 원소인
[6, 7, 8] 은 하나씩 C 에 추가
C:[1, 2, 3, 4, 5, 6, 7, 8]
풀이)
두 개의 배열을 합치기 위해서 각 배열의 값들을 하나씩 비교
더 작은 값을 새로운 배열에 하나씩 추가
한 배열이 끝나면 남은 배열의 모든 값을 새로운 배열에 추가
result 라는 새로운 배열을 만든 다음에, while 문을 이용해서 비교 이후에 값을 추가
array_a = [1, 2, 3, 5]
array_b = [4, 6, 7, 8]
def merge(array1, array2):
result = []
array1_index = 0
array2_index = 0
while array1_index < len(array1) and array2_index < len(array2):
if array1[array1_index] < array2[array2_index]:
result.append(array1[array1_index])
array1_index += 1
else:
result.append(array2[array2_index])
array2_index += 1
if array1_index == len(array1): # array2가 남아있다
while array2_index < len(array2):
result.append(array2[array2_index])
array2_index += 1
if array2_index == len(array2): # array1이 남아있다
while array1_index < len(array1):
result.append(array1[array1_index])
array1_index += 1
return result
print(merge(array_a, array_b)) # [1, 2, 3, 4, 5, 6, 7, 8]
나의 풀이)
array_a = [1, 2, 3, 4, 5]
array_b = [4, 6, 7, 8]
def merge(array1, array2):
merge_array = []
array1_index = 0
array2_index = 0
array1_len = len(array1)
array2_len = len(array2)
# array1과 array2 둘 중 하나가 끝 인덱스를 넘어갈 때까지 반복
while array1_index <= array1_len-1 and array2_index <= array2_len-1:
if array1[array1_index] < array2[array2_index]:
merge_array.append(array1[array1_index])
array1_index += 1
else:
merge_array.append(array2[array2_index])
array2_index += 1
# array2가 merge_array에 append를 모두 했음에도 불구하고 array1의 값들이 남아있는 상황
if array1_index > array1_len-1:
while array2_index <= array2_len-1:
merge_array.append(array2[array2_index])
array2_index += 1
# array1가 merge_array에 append를 모두 했음에도 불구하고 array2의 값들이 남아있는 상황
if array2_index > array2_len-1:
while array1_index <= array1_len-1:
merge_array.append(array1[array1_index])
array1_index += 1
return merge_array
print(merge(array_a, array_b)) # [1, 2, 3, 4, 5, 6, 7, 8]
분할 정복의 개념을 적용하여 '병합정렬'을 구현할 수 있음!
분할 정복(Divide and Conquer):
문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략
[5, 4] 라는 배열이 있다면
이 배열을 [5] 와 [4] 를 가진 각각의 배열로 작은 2개의 문제로 분리해서 생각하는 것임
그러면 이 둘을 합치면서 정렬한다면 결국 전체의 정렬된 리스트가 될 수 있음
이 개념을 조금 더 확대해서 생각해보면
[5, 3, 2, 1, 6, 8, 7, 4] 이라는 배열을
반으로 쪼개면
[5, 3, 2, 1] [6, 8, 7, 4] 이 됨
또 반으로 쪼개면
[5, 3] [2, 1] [6, 8] [7, 4] 이 됨
또 반으로 쪼개면
[5] [3] [2] [1] [6] [8] [7] [4] 이 됨
이 배열들을 두개씩 병합을 하면
[5] [3] 을 병합하면 [3, 5] 로
[2] [1] 을 병합하면 [1, 2] 로
[6] [8] 을 병합하면 [6, 8] 로
[7] [4] 을 병합하면 [4, 7] 로
[3, 5] 과 [1, 2]을 병합하면 [1, 2, 3, 5] 로
[6, 8] 와 [4, 7]을 병합하면 [4, 6, 7, 8] 로
[1, 2, 3, 5] 과 [4, 6, 7, 8] 를 병합하면 [1, 2, 3, 4, 5, 6, 7, 8] 이 됨
위의 과정을 보고 재귀함수가 떠오름!!!
MergeSort(시작점, 끝점)
MergeSort(0, N) = Merge(MergeSort(0, N/2) + MergeSort(N/2, N))
0부터 N까지 정렬한 걸 보기 위해서는 0부터 N/2 까지 정렬한 것과 N/2부터 N까지 정렬한 걸 합치면 됨
문자열의 길이가 1보다 작거나 같을 때 하나밖에 없으니까 무조건 정렬되었다고 볼 수 있을테니 탈출
def merge_sort(array):
if len(array) <= 1:
return array
mid = (0 + len(array)) // 2
left_array = merge_sort(array[:mid]) # 왼쪽 부분을 정렬하고
right_array = merge_sort(array[mid:]) # 오른쪽 부분을 정렬한 다음
merge(left_array, right_array) # 합치면서 정렬
[병합 정렬 - merge sort]
잘 모르겠다면 print문으로 출력해보면서 과정을 확인하기
array = [5, 3, 2, 1, 6, 8, 7, 4]
def merge_sort(array):
if len(array) <= 1:
return array
mid = len(array) // 2
left_array = merge_sort(array[:mid])
right_array = merge_sort(array[mid:])
# print(array)
# print('left_arary', left_array)
# print('right_arary', right_array)
return merge(left_array, right_array)
def merge(array1, array2):
result = []
array1_index = 0
array2_index = 0
while array1_index < len(array1) and array2_index < len(array2):
if array1[array1_index] < array2[array2_index]:
result.append(array1[array1_index])
array1_index += 1
else:
result.append(array2[array2_index])
array2_index += 1
if array1_index == len(array1):
while array2_index < len(array2):
result.append(array2[array2_index])
array2_index += 1
if array2_index == len(array2):
while array1_index < len(array1):
result.append(array1[array1_index])
array1_index += 1
return result
print(merge_sort(array)) # [1, 2, 3, 4, 5, 6, 7, 8]
[출력 결과]
[5, 3, 2, 1, 6, 8, 7, 4] 맨 처음 array 이고
left_arary [5, 3, 2, 1] 이를 반으로 자른 left_array
right_arary [6, 8, 7, 4] 반으로 자른 나머지가 right_array
[5, 3, 2, 1] 그 다음 merge_sort 함수에는 left_array 가 array 가 됨
left_arary [5, 3] 그리고 그 array를 반으로 자르고
right_arary [2, 1] 나머지를 또 right_array 에 넣은 뒤 반복
[5, 3]
left_arary [5]
right_arary [3]
[2, 1]
left_arary [2]
right_arary [1]
[6, 8, 7, 4]
left_arary [6, 8]
right_arary [7, 4]
[6, 8]
left_arary [6]
right_arary [8]
[7, 4]
left_arary [7]
right_arary [4]
[시간복잡도]
merge함수에서 while 문이 len(array1) 과 len(array2)의 길이 만큼 반복하고 있음
최대 len(array1) + len(array2) 만큼의 연산량이 필요한데
이의 최댓값은 O(N) !
array1과 array2 는 결국 array 를 반으로 잘라서 넣은 길이이기 때문
그러면 merge 함수의 시간 복잡도는 O(N)
merge_sort 함수는 대입 연산과 비교 연산 몇 번밖에 나오지 않으므로
상수의 시간 복잡도를 가짐
그렇지만 병합 정렬의 총 시간복잡도는 O(N)이라고 말하면 안됨!
1단계
[1, 2, 3, 4, 5, 6, 7, 8] 을 정렬하기 위해
[1, 2, 3, 5] 과 [4, 6, 7, 8] 을 병합
즉, 크기 N 인 배열을 정렬하기 위해
크기 N/2 인 부분 배열 2개를 비교
그러면 N/2 * 2 = N 번 비교하게 됨
2단계
[1, 2, 3, 5] 과 [4, 6, 7, 8] 을 정렬하기 위해
[3, 5] [1, 2] 과 [6, 8] [4,7] 을 병합
크기 N/2 인 부분 배열 2개를 정렬하기 위해
크기 N/4 인 부분 배열 4개를 비교
그러면 N/4 * 4 = N 번 비교하게 됨
3단계
[3, 5] [1, 2] 과 [6, 8] [4,7] 을 정렬하기 위해
[5] [3] [2] [1] [6] [8] [7] [4] 를 병합
크기 N/4 인 부분 배열 4개를 정렬하기 위해
크기 N/8 인 부분 배열 8개를 비교
그러면 N/8 * 2 = N 번 비교하게 됨
즉 모든 단계에서 N 만큼 비교
그러면 총 몇 단계인지만 알면 시간 복잡도를 구할 수 있음
크기가 N → N/2 → N/2^2 → N/2^3 → .... → 1
이 되는 순간이 있을것임
N/(2^K) = 1
k = log_2N
log_2N 번 반복하게 되면 1이 됨
이걸 수식으로 나타내면
N만큼의 연산을 logN 번 반복한다고 해서
log_2N * O(N) = O(Nlog_2N)
시간 복잡도는 총 O(Nlog_2N) -> O(NlogN) 이 됨!