[ Python_알고리즘 ] 분할정복법 ① 합병 정렬

#1부터 n까지의 합

def n_sum(start, end):
	sum_value = 0
    if start < end : 
    	for i in range( start, end+1 ) :
        	sum_value += i
    return sum_value
    
print(n_sum(1,100))


#분할 정복법

def n_sum(start, end):
	if start == end : 
    		return start
    	mid = ( start + end ) // 2
    
	return n_sum(start, mid) + n_sum(mid+1, end)

 

 

[ 합병 정렬 ]

 

리스트를 왼쪽, 오른쪽 반반 나누어주고 각각의 리스트를 각각 정렬한 후 하나의 리스트로 합병

 

def merge(list1, list2):
    
    i,j = 0,0
    final_list = list()
    
    while i < len(list1) and j < len(list2) :
        if list1[i] > list2[j] :
            final_list.append(list2[j])
            j+=1
        else :
            final_list.append(list1[i])
            i+=1

    if i == len(list1) : # list2에 남은 항목이 있을 경우
        final_list += list2[j:]
    elif j == len(list2) : # list1에 남은 항목이 있을 경우
        final_list += list1[i:]
    
    return final_list
    
    
def merge_sort(my_list) :
	if len(my_list) == 1 :
    		return my_list
        
    	mid = len(my_list) // 2
    	left_list = my_list[:mid]
    	right_list = my_list[mid:]
    
    	return merge(merge_sort(left_list), merge_sort(right_list))

print(merge_sort([17,4,8,9,12,34,90,67,1,6,45]))