2. 시작하기(1)

2.1 삽입정렬

정렬문제

입력 : n개 수들의 수열

출력 :

을 만족하는 입력 수열의 순열(재배치)

정렬하고자 하는 숫자를 키라고 한다.

의사코드와 “실제” 프로그램 코드의 차이는, 의사 코드에서는 알고리즘을 가장 분명하고 간결하게 서술할 수 있다면 어떤 표현 방법을 사용해도 좋음. 영어, 한글 문장등이 들어갈 수 도 있음. 데이터 추상화, 모듈화, 오류처리 등의 소프트웨어 공학 관점의 문제를 고려하지 않음.

삽입정렬 : 카드 놀이를 할 때 손에 쥔 카드를 정렬하는 것. 무작위로 있던 책상 위에서 하나를 꺼내 왼손 위에 이미 든 카드와 오른쪽에서 왼쪽 방향으로 차례로 비교. 입력된 원소를 적절한 위치로 정렬

insertion-Sort(A)

1
2
3
4
5
6
7
8
for j = 2 to A.length
	key == A[j]
    // A[j]를 정렬된 배열 A[1..j-1]에 삽입한다.
    I = j-1 5
    while i > 0 그리고 A[i] > key
    A[i+1] = A[i]
    i = i-1
    A[i+1] = key

루프 불변성(Loop Invariant)과 삽입 정렬의 타당성

인덱스 j는 왼손으로 가져가 정렬할 “현재 카드” 를 나타낸다. for 루프에서 인덱스 j로 표시되는 반복이 시작될 때 부분 배열 A[1, .., j-1]은 현재 손에 쥔 정렬된 카드이다. 부분 배열 A[ j + 1, .., n]은 아직 탁자에 쌓여 있는 카드다. 즉, A[1, .., j -1 ]은 처음에 탁자에 쌓인 순서대로 맨 앞부터 j -1번째까지의 값이지만 이제는 정렬되어 저장된 것.

이를 루프의 불변성(Loop invariant)이라 함.

1~8행의 부분 배열 A[1 .. j-1]은 원래 A[1.. j-1] 원소지만 for 루프가 반복을 시작할 때 마다 정렬된 순서로 구성

루프 불변성의 세가지 특성

초기조건 : 루프가 첫 번째 반복을 시작하기 전에 루프 불변성이 참이어야 한다.

유지조건 : 루프의 반복이 시작되기 전에 루프 불변성이 참이었다면 다음 반복이 시작되기 전까지도 계속 참이어야 한다.

종료조건 : 루프가 종료될 때 그 불변식이 알고리즘의 타당성을 보이는 데 도움이 될 유용한 특성을 가져야 한다.

초기조건, 유지조건을 만족한다 => 루프가 반복을 시작할 때 루프 불변성은 항상 참

수학적 귀납법과 유사하다.

1. 베이스 케이스: 첫 반복이 시작되기 전에 불변식이 만족함을 보이는 것 => 초기조건
2. 귀납적 단계 : 다음 반복으로 넘어갈 때 불변식이 만족함을 보이는 것 => 유지 조건

세 번째 특성이 가장 중요 => 루프 불변성을 보이는 목적이 알고리즘의 타당성을 보이는 것이기 때문!

일반적인 수학적 귀납법과 달리 루프가 종료될 때 귀납적 과정도 끝남.

루프 변성(loop variant)과 루프 불변성(loop invariant)

루프 불변성 : 각 루프의 반복 전후에 참이라는 조건이다. 루프의 각 반복이 ‘참’인 것이 루프의 실행 이후에도 바뀌지 않는다. 루프 불변성은 보통 알고리즘이 올바르게 작동하는 지를 증명하기 위해 사용된다.

루프 변성 : 루프가 종결되는 특정 값에 도달하기 전 까지 루프의 각 반복으로 증가하거나 감소하는 값이다. 루프 변성은 루프가 결국 종결되고 알고리즘이 무한 루프에 빠지지 않음을 보이기 위해 사용된다.

ex) 배열에서 특정 값을 탐색하는 알고리즘을 가정하자. 알고리즘은 값을 찾기 전까지 배열을 배회하는 루프를 사용한다.

• 루프 불변성 : 우리가 찾고 있는 값은 루프가 시작하기 전에 배열에 없다.
• 루프 변성 : 알고리즘이 최근에 본 배열의 index. 이 index는 배열의 끝에 도달하거나 값이 발견되기 전 까지 루프의 각 반복마다 1씩 증가한다.

ex) 삽입 정렬 알고리즘

초기 조건 : 루프의 첫 반복이 시작되기 전, 즉 j = 2일 때 루프 불변성이 성립하는지 살펴본다.¹

이때 부분 배열 A[1..j-1]은 A[1] 한 개의 원소로 구성되는데, 원래는 A[1]의 값이다. 게다가 그 부분 배열은 정렬되어 있으므로 루프의 첫 반복 시작 전에 루프 불변성이 성립한다.

유지 조건 : 다음으로 두 번째 특성, 즉 매 반복 시 루프 불변성이 유지되는지를 살펴본다. 간단하게 설명하면 for 루프의 바디 부분은 A[j]의 올바른 위치를 찾을 때까지 A[j-1],A[j-2],A[j-3], … 을 오른쪽으로 한 자리씩 이동시키는 작업을 한 뒤(4~7행), A[j]값을 적절한 위치에 삽입한다(8행). 그러면 배열 A[1..j]는 기존 배열 A[1..j]와 동일한 원소를 정렬한 상태로 갖게 된다. j가 1씩 증가하면서 for 루프의 다음 반복에서 루프 불변성이 유지된다.

(정확히는, 5-7행의 while 루프에 대한 루프 불변성도 증명해야 함)

종료조건 : 루프가 종료되었을 때 상황을 조사해본다. 삽입 정렬의 경우 for 루프는 j가 A.length = n보다 커질 때, 즉 j가 1씩 증가하므로 j = n+1일 때 종료된다. 앞의 루프 불변성의 기술에서 j에 n+1을 넣어보면 부분 배열 A[1..n]은 원래 A[1..n]의 원소로 구성되지만 정렬된 순서로 저장됨. A[1..n]이 전체 배열이므로 배열 전체가 정렬되었으며 이는 알고리즘이 타당함을 의미.

의사코드의 규칙(이 책)

• 들여쓰기는 블록 구조를 나타냄
• C++, 자바, 파스칼의 for문 : 루프 카운트 변수의 값 = 정의되지 않은 값 => for 루프를 처음으로 빠져나올 때의 값
• // : 주석
• i = j = e 는 i,j에 e 할당
• 명시하지 않은 변수는 지역 변수
• A[i]는 A의 i번째 값
• ”..”은 연속적인 부분
• 복합 데이터는 객체 형태, 객체는 필드로 구성(예 : A.length)

배열과 같은 객체를 나타내는 변수는 그 내용을 담고 있는 데이터에 대한 포인터로 다루어짐(예 : y=x 실행되면 y.f = x.f)

• 포인터가 아무 객체도 가리키지 않으면 NIL 이라는 특수값
• 프로시저(Procedure)의 매개변수들은 값에 의해 전달(call by value). 피호출 프로시저는 매개변수에 대해 복사본을 가지며, 피호출 프로시저에서 매개변수에 어떤 값을 할당하더라도 호출 프로시저에서 값의 변화를 모른다. 객체가 전달되면 객체의 데이터를 가리키는 포인터는 복사되지만 그 객체의 필드는 복사되지 않는다. (예: x가 피호출 프로시저의 매개변수 일 때 피호출 프로시저에서 x = y를 할당하는 것을 호출 프로시저에서는 확인할 수 없다. 그러나 x.f = 3과 같은 할당문은 호출 프로시저에서도 변화를 알 수 있다.)
• 이와 비슷하게 배열을 함수의 매개변수로 쓸 때는 배열 전체를 넘기지 않고 배열의 포인터만 넘긴다. 이 경우에도 배열의 원소값을 변화시키면 호출 프로시저에서 확인 할 수 있다.
• return문은 호출되는 즉시 호출 프로시저로 돌아간다. 대부분의 return문은 값을 호출 프로시저로 보낸다. 이 책의 의사코드에서는 많은 프로그래밍 언어들과 달리 하나의 return문으로 여러 값을 리턴할 수 있다.
• ‘and’와 ‘or’ 같은 이진 논리 연산자는 조기 차단할 수 있다. 즉, “x and y”문에서 x를 먼저 계산한다. x가 false면 식의 결과가 True가 될 수없으므로 y를 계산조차 하지 않는다. 반면, x가 true면 식의 결과를 계산하기 위해 y값도 반드시 계산해야 한다. 비슷하게 ”x or y”식에서 x의 결과값이 false일 경우에만 y를 계산한다. 이렇게 조기 차단되는 연산자를 사용하면 “x =/ NIL and x.f = y”와 같은 이진 논리 식에서 x가 NIL인 경우 x.f를 계산할 때 어떤 상황이 벌어질지 걱정하지 않고 사용할 수 있다.
• error는 프로시저가 호출되는 동안 조건이 잘못되어 오류가 발생함을 의미한다. 발생한 오류에 대한 처리는 호출 프로시저에서 이루어지므로 프로시저에서는 오류 처리를 명시하지 않는다.

• Next
  2. 시작하기(2)