[MIT 6.006] 3.Sets and Sorting

Set interface

아이템들의 순서가 없는 모든 원소가 unique한 집합이다

그렇다면 이 set interface를 수행하기 위한 data structure는 뭐가 좋을까?

후보 1. array

container	static	dynamic	order
build(x)	find(k)	insert,delete	find_min,max
O($n$)	O($n$)	O($n$)	O($n$)

위와 같이 array를 사용하게 된다면 set interface들은 모두 다 선형시간이 걸리게 된다

후보 2. Sorted Array

정렬된 배열을 사용하게 된다면 훨씬 빨라지는걸 확인할 수 있다.

container	static	dynamic	order
build(x)	find(k)	insert,delete	find_min,max
?	O($logn$)	O($n$)	O($logn$)

그치만 여전히 dynamic operation에서는 선형시간이 걸리지만 그냥 배열보다는 훨씬 빠르게 key를 찾는 동작을 수행한다.

Sorting

삽입정렬과 선택정렬은 비교적 작은 크기의 배열을 정렬할때 자주 사용되는 간단한 알고리즘이다.

두 알고리즘 모두 incremental 즉 증분적인 방식 그리고 제자리 정렬 방식이다.

Selection Sort

매 단계에서 가장 작은(또는 큰) 원소를 선택(selection) 해서 앞쪽(또는 뒤쪽) 으로 보내는 정렬 알고리즘이다.

• 각 단계에서 전체 남은 구간 중 최소값을 찾아
• 그 값을 현재 위치와 한 번만 교환

동작 원리

1. 배열의 전체 구간 중에서 가장 작은 값을 찾는다.
2. 그 값을 현재 정렬해야 할 위치(맨 앞) 의 값과 교환(swap) 한다.
3. 그 다음엔 나머지 구간(정렬된 구간 제외) 에서 같은 과정을 반복한다. (배열이 완전히 정렬될 때까지 계속)

def selection_sort(A):                
	for i in range(len(A)-1, 0, -1):	# O(n)
    	m = i							# O(1)
        for j in range(i):				# O(i)
        	if A[m] < A[j] :			# O(1)
            	m = j					# O(1)
        A[m], A[i] = A[i], A[m]			# O(1)
        
        

쉽게 비유하자면 선택 정렬은 “운동회 줄 세우기”처럼 선생님이 모든 학생을 한 바퀴 쭉 보며 가장 키 작은 학생을 맨 앞에 세우고, 그 다음엔 남은 학생 중 다음으로 키 작은 학생을 두 번째에 세우는 식으로 반복하다 보면 키 순서대로 줄이 완성됩니다

따라서 최악의 경우 시간복잡도는

• Compare : $O(n^2)$ 각 단계별로 최소값을 찾기 위해서 배열을 한번 훑어야되기 때문에
• Swap : $O(n)$ 각 단계에서 최솟값을 한 번만 앞으로 옮기기 때문이다

Insertion Sort

이미 정렬된 부분에 새원소를 적절한 위치에 삽입(insert)하면서 정렬하는 알고리즘이다.

• 현재 원소를 정렬된 부분의 올바른 위치로 삽입하기 위해 앞쪽 원소들과 비교(compare)
• 필요할 때마다 한 칸씩 오른쪽으로 이동(swap 아님, shift) 시킴

동작 원리

1. 두번째 원소부터 시작해서 하나의 원소를 선택한다.
2. 이 원소를 왼쪽의 정렬될 부분과 비교한다
3. 자신보다 큰 원소들을 한칸씩 오른쪽으로 이동시킨다.
4. 그 사이에 자신을 삽입한다.
5. 배열 끝까지 이 과정을 반복한다.

def insertion_sort(A):
	for i in range(1, len(A)):			# O(n)
    	j = i							# O(1)
        while j>0 and A[j] < A[j-1]		# O(1)
        	A[j], A[j-1] = A[j-1], A[j] # O(1)
			j -= 1						# O(1)

쉽게 비유하자면

insertion sort은 손에 든 카드를 정렬하는 과정과 같다. 새로운 카드를 받을 때 마다 손에 있는 카드 중 어디에 끼워 넣을지 위치를 찾아서 넣는 것과 동일한 원리이다.

따라서 최악의 경우 시간복잡도는

• Compare :
  - worst : $O(n^2)$ 삽입할 자리를 찾기 위해서 매번 전체 배열을 훑어야됨
  • best : $O(n)$ 이미 정렬된 경우에는 각 원소마다 한번만 비교하고 바로 종료
• Swap :
  - worst : $O(n^2)$
  - 최악의 경우 모든 원소를 shift를 매단계마다 해야될 수도 있다.
  • best : $O(1)$
    • 이미 정렬이 다 되어있는 경우

In-place and stability

선택 정렬과 삽입 정렬은 모두 in-place 알고리즘이다. 즉, 거의 일정한 양의 추가 공간만으로 구현할 수 있다.

• insertion sort은 stability한 sort이다. 즉 같은 값을 가진 원소들은 입력에서의 순서를 정렬 후에도 그대로 유지한다.
• 반면, selection sort은 동일 원소의 순서가 바뀔 수 있다.

Merge sort

병합 정렬은 배열을 절반으로 계속 나누고(divide)하고 나눈 배열들을 정렬하면서 병합하는(merge)하는 알고리즘이다.

• 큰 수의 항목을 정렬할때 점근적(asympototically)으로 빠른 정렬 알고리즘이다.

동작원리

1. 분할 (divide) : 배열을 절반으로 계속 나눈다
2. 정복 (Conquer) : 각각의 작은 배열을 정렬한다.
3. 병합 (Merge) : 두 개의 정렬된 배열을 하나로 합치면서 정렬된 상태를 유지한다.

def merge_sort(A, a=0, b=None)
	if b is None : 
    	b = len(A)
    if 1 < b-a : 					# 재귀 조건, 최소 집합에 2개 이상의 원소가 있도록 함 
    	c = (a+b+1)//2				# 중간점 계산
        merge_sort(A,a,c)			
        merge_sort(A,c,b)
        L,R = A[a:c],A[c:b] 		# 두 절반을 복사
        i,j = 0,0					# i는 왼쪽 배열의 현재 위치, j는 오른쪽 배열의 현재 위치
        while a < b : 				# 각 부분 배열의 끝까지 보기
        	if j>=len(R) or (i<len(L) and L[i] < R[j]) # 왼쪽 배열의 값이 더 작음
            	A[a] = L[i]			# 병합 결과 배열A에 해당 요소로 넣기
                i += 1				# i 인덱스 증가 
            else :
            	A[a] = R[j]			# 병합 결과 배열A에 해당 요소로 넣기
            	j += 1				# j 인덱스 증가 
            a += 1 					# 병합 배열 인덱스 증가
            
        

Recurrence

$T(n) = 2T(\frec{n}{2}) + \Theta(n)$
$T(n) = O(nlogn) $

이를 통해 merge sort은 앞선 selection sort과 insertion sort 보다 훨씬 빠르다는 것을 알 수 있다.

Builed a sorted array

이러한 정렬 알고리즘을 이용해서 정렬된 배열 기반의 set 구조를 완성할 수 있다.

data structure	container	static	dynamic	order
operation	build(x)	find(k)	insert,delete	find_min,max
array	n	n	n	n
sorted array	nlogn	logn	n	1 또는 log n

이렇듯 build하는거와 찾는 시간이 매우 단축된 걸 볼 수 있다.