안녕

앞선 시간에 merge sort에 대해 설명 드렸습니다. 이번에는 in-place 정렬로 merge sort하는 법을 보여드리겠습니다. 1. 코드 n = int(input()) S = list(map(int, input().split())) def mergesort(low, high): # 두 개로 분할함 if low < high: mid = (low + high) // 2 mergesort(low, mid) mergesort(mid+1, high) merge(low, mid, high) def merge(low, mid, high): # 병합함 i = low; j = mid + 1; U = list() while i

1. Merge Sort의 알고리즘 및 코드 Problem : n개의 원소를 가지고 있는 정렬되지 않은 리스트 S를 오름차순으로 정렬 input : n과 정렬되지 않은 리스트 S output : 정렬된 리스트 S Merge Sort의 알고리즘) 1. 배열을 반으로 분할한다. 2. 분할한 배열을 정렬한다 (배열에 원소가 2개 이상이면 merge sort를 재귀 호출하여 정렬한다) 3. 분할한 배열을 합병하여 정렬한다. 그러면 결국엔 정렬은 배열에 원소가 1개 일 때 일어나겠죠? 근데 원소가 하나밖에 없으면 정렬할 필요가 없습니다. 따라서 merge sort는 배열의 원소가 하나가 될 때까지 쪼개고, 쪼개진 그 배열을 정렬하면서 합병하는 알고리즘이라 볼 수 있겠습니다. 그러면 한 번 코드로 작성해보겠습니다...