병합 알고리즘 w/파이썬

first = [1,3,5] , second = [2,4]

두 배열을 [1,2,3,4,5]로 합치고 싶다.

 

각 배열의 처음 순서부터 비교하여

1 < 2 -> 1을 선택

3 > 2 -> 2를 선택

3 < 4 -> 3을 선택

5 > 4 -> 4를 선택

- > 그리고 마지막 남은 5를 처리한다.

#[?] 2개의 정수배열 합치기 : 오름차순 정렬 가정
#병합알고리즘 : 오름차순 정렬된 정수 배열 2개를 하나로 병합

#[1] input - 정렬되지 않은 배열인 경우 정렬이 필요함
first = [1,3,5]
second = [2,4]

m = len(first)
n = len(second)

merge = [0]* (m+n) #m+n자리만큼 병합데이터 들어갈 배열을 만듦
i = 0
j = 0
k = 0

#[2] process - merge
while (i < m and j < n): #둘다 배열의 끝에 도달할때까지
	if first[i] < second[j]: #작은값을 저장
		merge[k] = first[i]
		k += 1
		i += 1
	else:
		merge[k] = second[j]
		k += 1
		j += 1


while (i < m): #첫번째 배열 first의 끝에 도달하면
	merge[k] = first[i]
	k += 1
	i += 1

while (j < n): #두번째 배열 second의 끝에 도달하면
	merge[k] = second[j]
	k += 1
	j += 1

#[3] output
for item in merge:
	print(item, end = ",")
print()

반응형

while i < m and j < n 을 통해 적은 쪽의 배열 값들을 모두 다 배치하고

남은 떨이들을 while i < m, while j < n 두개 중 걸리는 하나에서 처리한다.

자릿수가 맞지 않을 까봐 만들어놓은 병합정렬의 장치.