Insertion sort, Merge sort

공부한 2가지의 sort Algorithm에 대해서 정리해 보겠다.

Sorting Problem

우선 문제에 대해서 정의해보자

• Input : keys, A sequence of $n$ number
• Output : A permutation(순열) of the inpurt sequence.

Insertion sort

Description

Insertion sort : insertion(삽입)을 활용한 sorting algorithm
Insertion : key와 정렬된 key의 리스트가 주어지면, 정렬된 순서를 유지하면서 키를 삽입하는 것.

Pseudo Code

for j = 2 to A.length :
	key = A[j] # j번째 숫자를 A[1,...,j-1]의 sorted list에 삽입.
    i = j-1
    while i > 0 and A[i] > key :
    	A[i+1] = A[i]
        i = i-1
        # insert할 자리를 찾을때까지 한칸씩 뒤로 당긴다.
    A[i+1] = key
    # 찾은 자리에 키를 insertion

Performance

How to analyze the running time of an algorithm?

• specific machine의 running time을 모두 비교하는 것은 불가능 하기 떄문에,
  우리는 Count the number of instructions used by the algorithm
• Instuctions
  • Arithmetic(산수) : add, sub, multiply, divide, remainder, floor, celing
  • Data movement : load, store, copy
  • Control : conditional branch, unconditional branch, subroutine call and return
• running time of an algorhitm : function of input size $n$, $T(n)$

Running time of insertion sort

• Best case : $\Omega(n)$
• Worst case : $O(n^2)$

Space consumption of insertion sort

• $\theta(n)$ space
• Moreover, the input numbers are sorted in place.

Merge sort

Description

Merge sort : merge를 활용한 sorting algorithm
Merge : Given two sorted lists of keys, generate a sorted lsit of the keys in the given sorted lists.

Pseudo code

MERGE(A,p,q,r):
    n1 = q - p + 1 # length of list L
    n2 = r - q     # length of list R
    for i = 1 to n1:
    	L[i] = A[p+i-1]
    for j =1 to n2
    	R[j] = A[q+j]
    L[n1+1] = inf
    R[n2+1] = inf
    # inf is Sentinel.
    i = 1
    j = 1
    for k = p to r :
    	if L[i] <= R[j] : # Compare
            A[k] = L[i]   # Move
            i = i + 1
     	else :
       	    A[k] = R[j]   # Move
            j = j +1

MERGE-SORT(A,p,r):
    if p <r :
    	q = (p+r)/2
        MERGE-SORT(A,p,q)
        MERGE-SORT(A,q+1,r)
        MERGE(A,p,q,r)

Performance

Running time of merge sort

• $\theta(n_1 + n_2)$ time
  • Main operations : compare and move
  • #comparison $\leq$ #movement
  • #movement = $n_1 + n_2$
• Divide : $\Theta(1)$
• Conquer : $2T(n/2)$
• Combine : $\Theta(n)$

  Total : $cnlgn + cn = \Theta(nlgn)$