10 - 1 . Recursion으로 Sort 코드 + Merge Sort 구현해보기

참.. Sorting이라는 것이 원리를 설명으로 들을 때는 이해가 되는데

 

이걸 코드로 Implement 하는 게 되게 어렵다.

 

그리하여 Sort 코드를 직접 다시 한 번 쳐보기로 한다.

 

근데 이게 코드를 치면서 느끼는게, 한 번 코드가 눈에 익어버리니까 내가 뭔가 창의적으로 코드를 한다는 느낌보단 외워서 친다는 느낌이 더 든다 ㅋㅋ;;; 이러나 저러나 어떻게든 도움이 되겠지~ 라는 마인드로 그냥 공부해보자

 

# insertion sort
lst1 = [1,-10,5,0,32,-100,99,-8,-7.7,3]
lst2 = [-5,-4,-1,-3,4,0,19,1]
​
def inse(list) -> None :
    for i in range(1,len(list)):
        val = list[i]
        j = i-1
        
        while j>=0 and list[j] > val :
            list[j+1] = list[j]
            j -= 1
        
        list[j+1] = val
inse(lst1)
inse(lst2)
print(lst1,lst2)
[-100, -10, -8, -7.7, 0, 1, 3, 5, 32, 99] [-5, -4, -3, -1, 0, 1, 4, 19]

 

 

문제의 #insertion_sort , 분명 내가 처음부터 타이핑한 코드이지만,

 

머리에 남아있던 코드의 잔여때문에 무의식적으로 코딩한 듯 하다  ㅜㅜ

 

# 내가 다시 쳐보는 Selection sort
lst1 = [1,-10,5,0,32,-100,99,-8,-7.7,3]
lst2 = [-5,-4,-1,-3,4,0,19,1]
​
def sel(list):
    for i in range(len(list)):
        smallest = i
        
        for j in range(i+1,len(list)):
            if list[j] < list[smallest] :
                smallest = j
        list[i],list[smallest] = list[smallest],list[i]
​
sel(lst1)
sel(lst2)
print(lst1,lst2)
[-100, -10, -8, -7.7, 0, 1, 3, 5, 32, 99] [-5, -4, -3, -1, 0, 1, 4, 19]

 

위 Selection Sort는 그래도 이해가 잘 됐다. 왜인지는 모르겠는데 Insertion Sort보다 더 직관적으로 잘 다가오는 느낌

 

이 코드를 Recursion으로 한 번 구현해본다면..???

 

# 내가 다시 쳐보는 Selection sort with Recursion
​
lst1 = [1,-10,5,0,32,-100,99,-8,-7.7,3]
lst2 = [-5,-4,-1,-3,4,0,19,1]
​
​
def rec(lst : list,i : int) -> None :
    
    #Base case
    if i <= 1 :
        return
    
    small = 0
    for j in range(1,len(lst)):
        if lst[small] > lst[j]:
            small = j
    lst[0], lst[small] = lst[small], lst[0]
    
    rec(lst[1:],i-1) # list를 Sorting하면 최종 결과가 동일 list sort가 아니라 그런가 이상하게 나온다
#     rec(lst[1:],i-1)
    
        
rec(lst1,len(lst1))
rec(lst2,len(lst2))
print(lst1,lst2)
[-100, -10, 5, 0, 32, 1, 99, -8, -7.7, 3] [-5, -4, -1, -3, 4, 0, 19, 1]

 

일단 나의 친구 #Copilot 과 함께 어찌어찌 Recursion을 구현하려 했으나,

 

처음엔 실패했다. 교훈 -> Sort를 Recursion으로 구현할 땐 최대한 list를 slicing하는 건 자제하자.

 

뭔가 하나의 list로 sort하는게 아니라 그런가 결과가 빠그라진다.

 

# INDEX를 건들고 나서야 얻은 완성코드


lst1 = [1,-10,5,0,32,-100,99,-8,-7.7,3]
lst2 = [-5,-4,-1,-3,4,0,19,1]
​
def rec(lst,i,index=0):
    if index == i: return
    
    small = index
    for j in range(index+1,i):
        if lst[j] < lst[small]:
            small = j
    lst[index],lst[small] = lst[small],lst[index]
    
    rec(lst,i,index+1)
    
rec(lst1,len(lst1))
rec(lst2,len(lst2))
print(lst1,lst2)
[-100, -10, -8, -7.7, 0, 1, 3, 5, 32, 99] [-5, -4, -3, -1, 0, 1, 4, 19]

 

Index를 건들면 Recursive하게 sort하는 코드를 얻을 수 있었다.

 

사실 뭐,, 내가 했다기보단 Copilot이 한 거다. 나는 보고 이해만 했을 뿐 ㅠㅠ

 

찾다보니 Find Smallest 부분도 Recursive하게 구현하던데 될라나?

 

​
lst1 = [1,-10,5]
lst2 = [-5,-4,-1,-3,4,0,19,1]
​
def find_small(lst,curr_min,j):
    
    if j > len(lst)-1:
        return curr_min
    elif lst[curr_min] > lst[j]:
            curr_min = j
    return find_small(lst,curr_min,j+1)
​
def rec(lst,i,index=0):
    if index == i: return
    small = find_small(lst,index,index+1) # Recursive 추가적용
    lst[index],lst[small] = lst[small],lst[index]
    rec(lst,i,index+1)
    
rec(lst1,len(lst1))
rec(lst2,len(lst2))
print(lst1,lst2)
[-10, 1, 5] [-5, -4, -3, -1, 0, 1, 4, 19]

 

아 이놈 코딩한다고 진이 빠졌다.

 

별 것도 아닌데, find_small 부분에 lst를 변수로 넣어주지 않아서 자꾸 Sorting이 되지 않는 다는 것..

 

함수를 선언할 때 함수 안에 쓰이는 모든 변수들에 대해선 Local하게 하나하나 다 집어넣어 주어야겠다.

 

그리고 대망의 Merge Sort 나머지 부분 코딩..

 

​
# 내가 작성해보는 Merge Sort
​
def merge_sort(list): 
    if len(list) <= 1:
        return list
    
    mid = len(list) // 2
    left_half = list[:mid]
    right_half = list[mid:]
    
    left_s = merge_sort(left_half)
    right_s = merge_sort(right_half)
    
    return merge(left_s,right_s)
    
​
def merge(left,right)->None:
​
    result = []
    i,j = 0,0
    
    while i<len(left) and j<len(right):
        if left[i] < right[j] :
            result.append(left[i])
            i = i+1
        else:
            result.append(right[j])
            j= j+1
    result.extend(left[i:])  # append 아니고 extend 다...
    result.extend(right[j:])
    
    return result
    
​
lst1 = [1,-10,5,0,32,-100,99,-8,-7.7,3]
lst2 = [-5,-4,-1,-3,4,0,19,1]
​
print(merge_sort(lst1))
        
​
[-100, -10, -8, -7.7, 0, 1, 3, 5, 32, 99]

 

내가 작성했다 하기도 민망하다.

 

공부하느라 시간은 많이 썼지만, 결국 copilot의 도움을 받았다 ㅠㅠ

 

이것도 공부의 일종이겠지...?

 

멀고도 험한 코딩의 길

 

잘 할 수 있을라나 몰겄다~~ 으아아악