2.1 삽입 정렬

2. 시작하기

• 삽입정렬
• 분할정복 + 병합 알고리즘

---

2.1 삽입정렬

 

정렬하고자 하는 숫자 = key

 

n의 크기가 작을 경우

삽입정렬 > 병합정렬 

 

루프 불변성

• 초기조건 : 루프가 첫 번째 반복을 시작하기 전에 루프 불변성이 참이어야 한다.
• 유지조건 : 루프의 반복이 시작되기 전에 루프 불변성이 참이었다면 다음 반복이 시작되기 전까지도 계속 참이어야 한다.
• 종료조건 : 루프가 종료될 때 불변식이 알고리즘의 타당성을 보이는데 도움이 될 유용한 특성을 가져야 한다.

 

수학 귀납적 과정과 유사

• 초기 조건: 불변식
• 유지 조건 : 불변식 만족
• 종료 조건 : 불변식 불만족

---

연습문제

2.1-1

삽입정렬 2.1-1

2.1-2

for j = 2 to A.length
	key = A[j]
    i = j - 1
    
    while i > 0  그리고 A[i] < key
    	A[i + 1] = A[i]
        i = i - 1
    A[i+1] = key

 

2.1-3

A = <a1, a2, ..., an>

def Search(v)
    for i = 1 to A.length:
        if A[i] == v
            break
            return i
    return NIL

초기 조건 : for 문 시작

유지 조건 : i가 1씩 커지면서 유지

종료 조건 : if 조건이 참일 경우 / i가 n까지 도달했을 경우

 

2.1-4

// C를 0 으로 초기화
for i = 1 to (A.length+1)
    C[i] = 0

for i = A.length to 1
    hap = A[i] + B[i]
    if hap == 0
        C[i] = hap
    else if hap == 1 and C[i] == 1
    	C[i] = 0
        C[i+1] = 1
    else if hap == 1 and C[i] == 0
    	C[i] = hap
    else // hap == 2
        C[i + 1] = 1