20_알고리즘(3)

병합정렬

구현

• 코드

  # 병합 정렬
  def merge_sort(nums):
      N = len(nums)
  
      if N <= 1:	#길이가 1이하이면 더이상 분할이 불가능
          return nums
  
      mid = N//2	#길이가 2이상이면 분할
      left_nums = nums[:mid]
      right_nums = nums[mid:]
  
      left = merge_sort(left_nums)	#분할한 왼쪽 리스트에 대해서 다시 병합정렬
      right = merge_sort(right_nums)	#분할한 오른쪽 리스트에 대해 다시 병합정렬
  	
      return merge(left, right)	#분할한 왼쪽, 오른쪽 리스트를 병합
  
  
  # 병합
  def merge(left, right):
      left_idx, right_idx = 0, 0
      L, R = len(left), len(right)
      merged_nums = []
  
      while left_idx < L and right_idx < R:
          if left[left_idx] <= right[right_idx]:
              merged_nums.append(left[left_idx])
              left_idx += 1
          
          else:
              merged_nums.append(right[right_idx])
              right_idx += 1
  
      for i in range(left_idx, L):
          merged_nums.append(left[i])
  
      for j in range(right_idx, R):
          merged_nums.append(right[j])
  
      return merged_nums
  
  
  print(merge_sort([19, 10, 3, 5, 13, 4, 12, 17, 8, 16]))

재귀함수의 구조

• 재귀함수는 보통 종료조건 - 연산 - 반환값의 구조를 가짐
• 종료조건이 없거나 정상적이지 않다면 stack overflow가 발생할 때까지 호출이 계속 될 것이므로 종료조건을 잘 설정해주는 것이 중요
• 병합정렬의 경우 하나의 리스트를 더 이상 분할할 수 없을 때까지 분할한 후 정렬을 하며 병합하는데, 이 경우 "리스트의 분할이 더 이상 불가능한 경우"가 종료조건이 됨
• 종료조건에 해당하지 않는 경우에는 계속해서 절반으로 나누고 나눈 리스트 각각에 대하여 다시 정렬을 수행해야하므로, 절반으로 분할하고 각각에 대해 다시 재귀적으로 함수를 실행하는 것이 연산 부분이 됨
• 마지막으로 정렬된 양쪽의 리스트를 병합하는 것이 반환값에 해당

퀵정렬

• 퀵 정렬은 평균 시간복잡도 O(N logN)으로 좋은 성능을 가진 정렬 알고리즘이지만, 최악의 경우 O(N^2)의 시간복잡도를 가짐
• 이러한 시간복잡도의 차이는 어떤 요소가 pivot으로 선택되었는지에 따라 갈리기 때문에 pivot을 선택하는 방법 역시 퀵 정렬의 중요한 요소

pivot 선택 방법

1. random pivot 선택
2. Median-of-three 방법
   • random한 index 3개를 뽑고, 각 index가 가리키는 원소들의 median 값으로 pivot을 설정
3. 이 외에도 다양한 방법들이 있다고 함