Chpater 1 & 2

Insertion sort

INSERTION-Sort(A, n)
for i = 2 to n
	key = A[i]
    //Insert A[i] into the sorted subarray A[1 : i-1].
    j = i - 1
    while j>0 and A[j] > key
    	A[j+1] = A[j]
        j = j-1
        
   	A[j+1] = key

 A[1 : i-1] 까지는 loop invariant(루프 불변성) 이 성립됩니다.

적은 수의 원소를 정렬할 때는 효율적임

 

Merge Sort

Merge(A, p, q, r)
	n_l = q - p + 1 //중간점 p를 중심으로 왼쪽
    n_r = r - q // 중간점 p + 1부터 q까지 오른쪽
    새 배열 L[0..n_l - 1] and R[0 : n_r-1] 
    for i = 0 to n_l - 1 //A[p:q]를 L[0:n_l - 1] 에 copy
    	L[i] = A[p + i]
	for j = 0 to n_r - 1 //A[q+1:r] 을 R[0:n_r - 1]에 copy
    	R[j] = A[q + j + 1]
   i = 0 // L 배열을 가리킬 index
   j = 0 // R 배열을 가리킬 index
   k = p // A 배열을 가리킬 index
   
while i < n_l and j < n_r
   	if L[i] <= R[j] //오른쪽 배열이 더 크므로 왼쪽 배열을 먼저 집어넣음
    	A[k] = L[i]
        i = i + 1
	else A[k] = R[j]
    	j = j + 1
	k = k + 1
    
while i < n_l //L배열에 남은 것들 다 A배열에 넣기
	A[k] = L[i]
    i = i + 1
    k = k + 1
while j < n_r //R 배열에 남은 것들 다 A 배열에 넣기
	A[k] = R[j]
    j = j + 1
    k = k + 1

MERGE-Sort(A, p, r)
	if p >= r
    	return
	q = ceil((p + r) / 2)
    MERGE-Sort(A, p, q)
    MERGE-Sort(A, q + 1, r)
    
    MERGE(A, p, q, r)

시간복잡도는 O(nlogn)