보초법(Sentinel method)

보초법(Sentinel method)

보초법은 프로그램을 빠르게 만들어주는 방법 중 하나이다. 어떤 조건을 만족하는 데이터를 검색할 때 그 조건을 만족하는 것으로 보이는 데이터를 미리 배열 끝에 추가하면 배열 끝에 도달하는 과정을 생량할 수 있어서 프로그램의 처리 속도가 빨라진다.

보초법을 사용하지 않으면 검색하고 있는 데이터가 찾고자하는 데이터인지 확인하는 동시에 지금 검색하고 있는 데이터가 배열 밖인지도 확인해야한다. 찾고자하는 데이터가 배열 안에 없으면 배열 밖으로 나가기 때문이다. 그러나 검색을 시작하기 전에 배열의 끝에 찾고자하는 데이터를 넣어두면 반드시 데이터를 반드시 찾을 수 있으므로 배열 밖으로 나갔는지 나가지 않을지 확인하지 않아도 된다.

보초법은 삽입 정렬이나 퀵 정렬 같은 정렬 알고리즘에서 사용한다.

삽입 정렬의 시간 복잡도가 최악일 때

정렬하고자 하는 순서와 반대로 정렬되어 있는 경우 가장 느리다.

총 비교 횟수는 1/2n(n-1)회 이다.

1/2n(n-1)
= 1/2n^2 - 1/2n
= n^2 + n	// 계수 생략
= n^2		// 주요 항만 남김
= O(n^2)

총 데이터 이동 횟수는 1/2(n+1)n-1회 이다.

1/2(n+1)n - 1

= 1/2n^2 + 1/2n -1
= n^2 + n + 1 // 계수 생략
= n^2 // 주요 항만 남김
= O(n^2)

O 표기법: 데이터를 비교, 이동할 때 걸리는 시간

a * 비교 횟수 + b * 이동횟수
= [a * (1/2)n(n-1)] + [b * ((1/2)n+1)n - 1)]
= [(a/2)n^2 - (a/2)n] + [(b/2)n^2 + (b/2)n - b]
= (a/2 + b/2)n^2 + (b/2 - a/2)n - b
= n^2 + n + 1		// 계수 생량
= n^2				// 주요 항만 남김
= O(n^2)

사용하는 컴퓨터에 따라 다르지만 정렬하는 데이터의 수가 적을 때에는 O(n log n)알고리즘보다.
삽입 정렬 쪽의 속도가 더 빠를 수 있다. 그러므로 데이터가 대량일 때는 O(n log n)의 퀵 정렬이나 병합 정렬을 사용하고, 정렬하는 동안 데이터를 작게 나눠서 비교하고 이동할 때에는 삽입 정렬을 사용한다.

선택 정렬

선택 정렬은 남아있는 데이터 가운데 가장 작은 값 또는 가장 큰 값처럼 가장 적합한 값을 찾아서 찾아서 배열 끝으로 이동시키면서 정렬한다.

선택은 Selection인데 이 단어에는 '도태'라는 뜻도 담겨있다. 선택 정렬에서 가장 적당한 데이터를 꺼내는 방식은 마치 도태되는 과정과도 비슷하다.

그럼 가장 작은 값 혹은 가장 큰 값은 어떻게 구할까? 맨 앞에 있는 데이터를 복사해두고 차례대로 조사하면서 더 작이나 더 큰 값이 나오면 복사해둔 값을 갱신하는 식으로 찾는다.

선택 정렬의 시간 복잡도