CH6. 정렬 개념정리 (part 2)

O($n*logN$)의 시간 복잡도: 병합, 퀵 정렬

1. 퀵 정렬 (quick sort)

• 시간 복잡도 (평균적): O($n*logN$)
• 시간 복잡도 (최악): O($n^2$)

작동 방식

• 그룹을 둘로 나누어 재귀 호출 (병합 정렬과 유사)
• 그룹을 나눌 때 미리 정한 기준 (pivot)과 비교해서 나눈다 (병합 정렬과 차이)
• 기준(pivot): 주어진 값 중에 1개 선택
• 즉, 먼저 기준과 비교해서 그룹을 나누 후 재귀 호출해 합친다.
• 퀵 정렬은 오히려 정렬되어 있을 경우 최악의 경우를 맞을 수 있다.

대표적인 기준 값 (pivot) 선택 방식

랜덤 방식: N 개 중 임의의 위치

• 최악의 확률은 매우 줄어드나 확률(실행)에 따라 크게 달라질 수 O

중값 위치 (Middle Index)방식: 배열의 중간 위치 → length(arr)/2

• 정렬되어 있는 경우 최악을 피한다
• 일반적인 분포 (마지막, 1st값이 중간 값일 경우)에 취약할 수 O

중간 값 (Median)방식: 앞, 뒤, 중간 위치 중 중간 크기의 값이 있는 위치 사용

• 최악의 상황은 면할 수 있다
• 가장 많이 사용되는 방식
• [1, 3, 5, 7, 11, 13, 15, 17, 19] → 1, 11, 19 중에서 11이 중간 값이므로 11의 위치를 사용

코드1

# 퀵 정렬 1 (5주 1차 수업)
def quick_sort1(a):
    n=len(a)
    if n<=1:
        return a               # 재귀 종료 조건
    
    pivot=a[-1]                # 편의상 리스트의 마지막 값을 기준 값으로 정함
    g1=[]
    g2=[]

    # 파티셔닝: pivot을 기준으로 큰수와 작은 수를 좌우로 나눔 (partition) 
	#           -> pivot의 위치 return 
    for i in range(n-1):       # 마지막 값은 기준 값이므로 제외
        # 기준 값과 비교
        if a[i] <pivot:
            g1.append(a[i])    
        else:
            g2.append(a[i])
    return quick_sort1(g1)+[pivot]+quick_sort1(g2)

d=[6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
print(quick_sort1(d))   # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

코드2

# 출처: YouTube 알고리즘 강의
array1=[5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
    # 원소가 1개인 경우 종료 
    if start>=end: return   

    pivot=start       # pivot은 첫번째 원소
    left=start+1      # pivot보다 큰 데이터 담는 index
    right=end         # pivot보다 작은 데이터 담는 index

    while(left<=right):
        #  pivot보다 큰 데이터를 찾을 때까지 반복 
        # (pivot보다 작으면 left index를 바꾸면서)
        while(left<=end and array[left]<=array[pivot]):
            left+=1

        # pivot보다 작은 데이터를 찾을 때까지 반복 
        # (pivot보다 크면 right index를 바꾸면서)
        while(right>start and array[right]>=array[pivot]):
            right-=1

        # 엇갈렸다면 작은 데이터와 피벗 교체
        if (left>right):
            array[right], array[pivot]=array[pivot], array[right]
            
        # 엇갈리지 않았다면 작은 데이터와 큰 데이터 교체
        else:
            array[left], array[right]=array[right], array[left]

    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행 
    # 재귀 호출  
    quick_sort(array, start, right-1)
    quick_sort(array, right+1, end)

quick_sort(array1, 0, len(array1)-1)

# 오름차순 정렬된 것 확인 가능
print(array1)    # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

---

2. 병합 정렬 (Merge Sort)

분할 정복 방식으로 설계된 알고리즘으로 큰 문제를 반으로 쪼개서 문제 해결

작동 방식

• 분할 과정

  • 현재 배열을 반으로 쪼개 배열의 시작 위치, 종료 위치를 입력받아 2개를 더한 후 2로 나눠 그 위치를 기준으로 나눈다
  • 이를 쪼갠 배열의 크기가 0 or 1일때 까지 반복

• 합병 과정

  • 2 배열 A, B의 크기를 비교한다. 각 배열의 현재 index를 i, j로 가정
  • i: A배열의 시작 index & j: B 배열의 시작 주소
  • 오름차순의 경우 A[i]와 B[j] 중 작은 값을 배열 C에 저장. A[i]가 더 크다면 A[i] 값을 배열 C에 저장하고 i값을 1 증가
  • 이를 i나 j 2중 1개가 각 배열에 끝에 조잘할 때까지 반복
  • 끝까지 저장 못한 배열의 값을 순서대로 전부 C에 저장
  • C 배열을 원래 배열에 저장

코드

array = [8,4,6,2,9,1,3,7,5]

# 분할 과정
def merge_sort(array):
	if len(array) < 2:      # 배열 길이가 1 이하일 경우 종료
		return array
	mid = len(array) // 2
	low_arr = merge_sort(array[:mid])
	high_arr = merge_sort(array[mid:])

	merged_arr = []  # 작은 수 저장하는 배열
	l = h = 0
	while l < len(low_arr) and h < len(high_arr):
		if low_arr[l] < high_arr[h]:
			merged_arr.append(low_arr[l])
			l += 1
		else:
			merged_arr.append(high_arr[h])
			h += 1
	merged_arr += low_arr[l:]
	merged_arr += high_arr[h:]
	return merged_arr

array = merge_sort(array)

---

힙 정렬 (Heap Sort)

최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법

• 내림차순 정렬을 위해서는 최대 힙을 구성.
• 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.
• 장점: 삽입 성능이 배열이나 연결 리스트 기반 보다 좋다.
  * 힙은 자식 노드의 index를 알면 부모 노드의 index를 바로 알 수 있다.
  

과정 설명

• 정렬해야 할 n개의 요소들로 최대 힙(완전 이진 트리 형태)을 만든다.
• 내림차순을 기준으로 정렬
• 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장.
• 삭제되는 요소들(최댓값부터 삭제)은 값이 감소되는 순서로 정렬되게 된다.

자료구조 힙

힙 순서 속성을 만족하는 완전 이진 트리

Min Heap (최소힙)

• 순서 속성: 트리 내 모든 노드에 저장된 값은 자식 노드 이하.
• 힙에서 가장 작은 데이터를 갖는 노드는 루트 노드이다.
• 가장 작은 것을 위로 올리면서 이동
  • 삽입: 자식 노드가 부모보다 작으면 가장 작은 자식 노드와 부모 위치 switch
  • 삭제: 마지막 리프 노드를 루트로 이동 후 자식 중 가장 작은 것이 부모 노드로 올라옴

Max Heap (최대힙)

• 순서 속성: 트리 내 모든 노드에 저장된 값은 자식 노드 이상.
• 힙에서 가장 큰 데이터를 갖는 노드는 루트 노드이다.
• 가장 큰 것을 위로 올리면서 이동
  • 삽입: 자식 노드가 부모보다 작으면 가장 큰은 자식 노드와 부모 위치 switch
  • 삭제: 마지막 리프 노드를 루트로 이동 후 자식 중 가장 큰 것이 부모 노드로 올라옴

코드1

import heapq

# 계산복잡도: O(n*log(N))

# 이 부분 다시 확인 필요
# best case: O(N)... 정확하게 순서대로 위치해 있을 때 sort가 실제로 1번도 진행 X

def heap_sort(nums):
    heap=[]
    for num in nums:
        heapq.heappush(heap, num)

    sorted_nums=[]
    while heap:
        sorted_nums.append(heapq.heappop(heap))
    return sorted_nums

print(heap_sort([6, 8, 3, 9, 10, 1, 2, 4, 7, 5]))

코드 2

import heapq   # 최소 힙
heap=[]

# 숫자를 삽입
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)

# 최소 힙으로 트리구조 배열 출력
print(heap)                      # [1, 3, 7, 4]
print(heapq.heappop(heap))       # 1

print(heap)                      # [3, 7, 4]
print(heapq.heappop(heap))       # 3
print(heapq.heappop(heap))       # 7
print(heap[0])                   # 4

"""
heapq.heapify: 기존의 리스트를 힙으로 만드는 함수
"""
heap2=[4, 1, 7, 3, 8, 5]
heapq.heapify(heap2)
print(heap2)                  # [1, 3, 5, 4, 8, 7]

---

계수 정렬 (Count Sort)

• 특정한 조건이 부합할 때문 매우 빠르다.

  데이터의 크기 범위가 제한되어 정수 형태로 표현 가능할 때만 사용 가능하다.
  일반적으로 "(가장 큰 데이터) - (가장 작은 데이터) <1,000,000" 일 때 효과적으로 사용 가능