Juwan Park :: 병합 정렬 (파이썬)

병합 정렬 (파이썬)

★프로그래밍/Python :: 2016.08.25 20:26

파이썬으로 병합 정렬 알고리즘을 구현한 예제입니다.

병합 정렬에 대한 설명은 이미 루비로 병합 정렬 구현하기 포스트에서 했으니 여기서는 따로 하지 않겠습니다.

코딩 구조를 보면 루비와 비슷하다고 느껴질 수도 있겠으나 둘은 엄연히 다른 언어입니다.

파이썬 병합 정렬 코드를 일단 짜 보자면...

def merge_sort(a):
	if len(a) <= 1: return a
	# 배열 개수가 1 이하이면 그냥 리턴, 아니면 계속 진행
	half = len(a) // 2    # 개수에서 2를 나눔 (소수점 버림)
	L = merge_sort(a[:half])   # 왼쪽은 앞의 반만
	R = merge_sort(a[half:])   # 오른쪽은 앞의 반 제외
	mer = []                   # 정렬 결과 저장될 배열
	
	while len(L) > 0 and len(R) > 0:
		if L[0] > R[0]:  # 왼쪽이 오른쪽보다 크다면
			mer.append(R[0])
			R.pop(0)     # R의 0번을 결과배열에 넣고 R에서 삭제
		else:            # 그 외에는
			mer.append(L[0])
			L.pop(0)     # L의 0번을 결과배열에 넣고 L에서 삭제
	# L과 R 중 한쪽이 다 없어지고 남은 원소를 마저 넣음
	if len(L) > 0: mer += L
	if len(R) > 0: mer += R
	# 그 결과를 돌려줌
	return mer

루비로 구현했을 때와 알고리즘 구현 방식이 얼추 비슷해 보입니다.

이것도 한 번 해 보겠습니다.

arr = [7, 1, 4, 6, 10, 2, 14, 16, 13, 11, 15, 9, 12, 5, 8, 3]
print(merge_sort(arr))
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

역시 루비로 구현했을 때와 같은 결과가 나옵니다.

루비의 배열 원소 삽입/삭제 메소드가 파이썬에도 있어서 루비로 구현할 때와 비슷한 방식으로 구현이 가능합니다.

많은 도움 되셨나요?

유용한 정보로 활용하시기를 바랍니다.

Today 0    Yday 48    Tot 56,858
Juwan Park
Juwan Park's blog is powered by Daum and TISTORY.
Contemporary Blue for TISTORY.
Designed by Juwan Park. Creative Commons License
▲ TOP