20_알고리즘(3)

ryu·2023년 5월 25일
0

병합정렬

구현

  • 코드

    # 병합 정렬
    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. 이 외에도 다양한 방법들이 있다고 함

0개의 댓글