병합하기
병합은 array_a와 array_b의 값들을 1과4, 2와 4, 3과 4, 5와 4, 5와 6 이런 식으로 비교하여 작은 값들을 순서대로 새로운 배열에 넣어주어 정렬하는 과정으로 병합 정렬에서 이와 같은 방법이 사용된다.
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):
# 더 작은 값을 result에 붙여준다
if array1[array1_index] < array2[array2_index]:
result.append(array1[array1_index])
array1_index += 1
else:
result.append(array2[array2_index])
array2_index += 1
# 배열 한 개만 남았을 때
# array_2가 남았을 때
if array1_index == len(array1):
while array2_index < len(array2):
result.append(array2[array2_index])
array2_index += 1
#array_1이 남았을 때
if array2_index == len(array2):
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] 가 되어야 합니다!
병합정렬
각 값들을 반씩 쪼개서 배열에 넣고 재귀함수를 사용하여 하나가 될 때 까지 계속 쪼갠 후, 위에서 구현한 merge함수를 사용하여 다시 병합한 후, 값들을 정렬하고, 다시 병합하는 방법을 반복하여 모든 값들이 정렬 될 때 까지 수행하는 정렬 방법이다.
이 정렬의 시간 복잡도는 O(NlogN)으로 선택,버블,삽입정렬 보다는 복잡하지만 효율적인 정렬 방법이다.
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:])
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] 가 되어야 합니다!