출처: 위키피디아
mergesplit 함수 만들기
merge 함수 만들기
def split_func(data_list):
medium = int(len(data_list) / 2)
print (data_list[:medium])
print (data_list[medium:])
data_list = [1, 2, 3, 4, 5]
split_func(data_list)
다음 문장을 코드로 작성해보기 (merge함수는 아직은 없는 상태, 있다고만 가정) * mergesplit 함수 만들기 - 만약 리스트 갯수가 한개이면 해당 값 리턴 - 그렇지 않으면, 리스트를 앞뒤, 두 개로 나누기 - left = mergesplit(앞) - right = mergesplit(뒤) - merge(left, right)
def mergesplit(data_list):
if len(data_list) == 1:
return data_list
medium = int(len(data_list) / 2)
left = mergesplit(data_list[:medium])
right = mergesplit(data_list[medium:])
return merge(left, right)
다음 경우만 프로그래밍으로 작성해보기 left = [0] right = [3] 결과는 별도의 리스트 변수를 만들어 적은 숫자 순으로 순서대로 저장해서 리턴
다음 경우만 프로그래밍으로 작성해보기 left = [0, 2] right = [1] 결과는 별도의 리스트 변수를 만들어 적은 숫자 순으로 순서대로 저장해서 리턴
다음 경우만 프로그래밍으로 작성해보기 left = [0, 2] right = [1, 3] 결과는 별도의 리스트 변수를 만들어 적은 숫자 순으로 순서대로 저장해서 리턴
1. sorted_list 리스트 변수 선언하기 2. left_index, right_index 를 0 으로 초기화 하기 3. while left_index < len(left) or right_index < len(right) 이면, - 만약 left_index >= len(left)이면, sorted_list 에 right[right_index] 를 추가하고, right_index 값을 1증가 - 만약 right_index >= len(right)이면, sorted_list 에 left[left_index] 를 추가하고, left_index 값을 1증가 - 만약 left[left_index] < right[right_index]이면, sorted_list 에 left[left_index] 를 추가하고, left_index 값을 1증가 - 위 세가지가 아니면, sorted_list 에 right[right_index] 를 추가하고, right_index 값을 1증가
import random
data_list = random.sample(range(100), 10)
def mergesplit(data_list):
if len(data_list) <= 1:
return data_list
medium = len(data_list) // 2
left = mergesplit(data_list[:medium])
right = mergesplit(data_list[medium:])
return merge(left, right)
def merge(left, right):
merged = list()
left_point, right_point = 0, 0
# case1 - left/right 둘다 있을때
while len(left) > left_point and len(right) > right_point:
if left[left_point] > right[right_point]:
merged.append(right[right_point])
right_point += 1
else:
merged.append(left[left_point])
left_point += 1
# case2 - left 데이터가 없을 때
while len(left) > left_point:
merged.append(left[left_point])
left_point += 1
# case3 - right 데이터가 없을 때
while len(right) > right_point:
merged.append(right[right_point])
right_point += 1
return merged
mergesplit(data_list)