공룡호가 사는 세상 이야기

어떤 명령어의 수행시간을 측정하고 싶을때가 있다.
이때 유용하게 사용할수 있는 함수가 GetTickCount()이다.

GetTickCount()함수는 시스템이 시작 된 후 얼마의 시간이 경과했는지를 반환한다. 단위는 밀리세컨드 단위이다. 참고로 경과시간은 DWORD(32비트 값)이므로 최대 49.7일이 지나면 다시 0으로 된다고 한다.

The GetTickCount function retrieves the number of milliseconds that have elapsed since the system was started. It is limited to the resolution of the system timer. To obtain the system timer resolution, use the GetSystemTimeAdjustment function.

DWORD GetTickCount(void);

Parameters : This function has no parameters.
Return values : The return value is the number of milliseconds that have elapsed since the system was started.


#include <iostream>
#include <windows.h> //GetTickCount()함수 이용을 위해 추가한다.

using namespace std;

void main()
{
long startTime = GetTickCount(); //현재 시각을 저장한다.(시작지점)

for(int i=0; i<100000; i++) //시간 딜레이를 주기 위해 i값을 출력한다.
cout<<i<<endl;; //여기서는 테스트 하기 위한 명령어라고 보면 된다.

long endTime = GetTickCount(); //현재 시각을 저장한다.(종료지점)
long tickDiff = endTime - startTime; //수행시간 = 종료시각 - 시작시각
long secDiff = tickDiff / 1000 ; //이건 초단위로도 나타내기 위한 것.

cout<<"Start Time : "<<startTime<<"ms"<<endl; //시작시각
cout<<"End Time : "<<endTime<<"ms"<<endl; //종료시각
cout<<"Tick difference : "<<tickDiff<<"ms"<<endl; //밀리세컨드 단위
cout<<"Second difference : "<<secDiff<<"s"<<endl; //초단위
}

'프로그래밍' 카테고리의 다른 글

ACM 10018 Reverse And Add  (0) 2006.01.16
ACM 10127 ONES  (0) 2006.01.16
chaos in FOR loop  (0) 2006.01.13
ACM 10110 Light, More Light  (0) 2006.01.13
ACM 100 3n+1 Problem  (2) 2006.01.10

for (expr1; expr2; expr3)
statement;
next statement;

굉장히 많이 쓰는 루프문이라서, 전부 알고 있다고 생각했는데 그것이 아니었다. expr1의 값으로 for루프를 최소 한번은 실행한다고 생각했는데, 그것이 아니었다.
내가 알고 있던 것은 expr1로 statement를 실행한 다음 expr3 을 수행하고, expr2 수식을 평가하여 참이면 다시 루프를 수행하는 것이었는데, 시간이 지나면서 착각을 일으킨 것일까.
expr1이 expr2의 조건을 만족하지 않는다면, 단 한번도 실행되지 않는다.

여기서 expr2를 사용하고 for루프의 몸체에 continue 문장이 없다면, 이것은 다음과 완전히 동일하다.

expr1;
while (expr2) {
statement;
expr3;
}
next statement;

보라, expr1은 먼저 expr2를 평가하고, 만족하지 않으면 next statement로 바로 이동하는 것을 볼 수가 있다.

어렵지 않게 찾아낼 수 있던 것이었지만, 반복루프와 함수 안에 갖혀서 찾아낼 수가 없었다.... 덕분에 하루종일 삽질했다. -_-
기본적인, 함수와 키워드의 사용에 익숙해 지다 보면, 내가 사용하는 방법이 전부이며 그것이 반드시 맞을 것이라는 착각에 빠지게 된다.
에러를 찾을 수 없을 때, 프로그래머는 첫줄부터 다시 읽어 나가지만 자신의 착각속에서 이루어지는 디버그는 의미가 없다.

'프로그래밍' 카테고리의 다른 글

ACM 10127 ONES  (0) 2006.01.16
GetTickCount() Function  (1) 2006.01.16
ACM 10110 Light, More Light  (0) 2006.01.13
ACM 100 3n+1 Problem  (2) 2006.01.10
오각수 구하기  (0) 2006.01.10

ACM - 10110
Programming Challenges - 110701


우리 학교의 어떤 복도는 전구마다 불을 켜고 끄는 스위치가 있다. 불이 꺼져 있을때 스위치를 누르면 불이 켜지고 다시 스위치를 누르면 불이 꺼진다. 처음에는 모든 전구가 꺼져 있다.

복도에 n개의 전구가 있을 때, 복도를 n번 왕복하면서 i 번째 갈 때 i 로 나누어 떨어지는 숫자의 위치에 있는 스위치를 누르고 돌아올 때는 누르지 않는다.

이런 식으로 스위치를 누를 때 n개의 전구가 있을 때 n번 왕복하며 스위치를 누를 때 가장 마지막 전구의 상태를 출력하는 프로그램을 작성하자.

입력
전구의 수를 나타내는 정수 (2^32 - 1 이하) 를 입력하고, 출력한다.

출력
전구가 켜져 있으면 "Y"를 꺼져 있다면 "N"를 출력한다.

입력 예제
3
6241
8191

출력 예제
N
Y
N

손쉽게 아래 알고리즘을 설계할 수 있다.
어차피 마지막 전구의 상태만 출력할 수 있으면 되므로, 다른 전구가 켜지든 말든 상관하지 않아도 된다.
따라서 1부터 N까지의 정수로 N을 하나씩 나누어 보면서
나누어 떨어지는 숫자가 나올 때 마다 bool값의 스위치값을 반대로 설정해 주고, 끝나면 스위치 값을 화면에 뿌려주면 된다...
하지만 속도를 개선해야 한다면? 일단 다음 소스를 보자...

#include <stdio.h>

char switch_light(int n)
{
bool onoff = false; //초기 전구값

for (int i=1; i<=n; i++)
{
if (n % i == 0) //마지막 전구만 알아내면 된다.
{//꺼져있으면 켜고, 켜져있으면 끈다.
if (onoff == false)
onoff = true;
else
onoff = false;
}
}

if (onoff == true) //마지막 전구값 리턴
return 'Y';
else
return 'N';
}


void main(void)
{
int n;
scanf("%d", &n);

printf("%c\n", switch_light(n));
}

사람이 생각하는 방식과 똑같이 구현된 알고리즘이다.
한번씩 지나가면서 마지막 전구만 켜고 끄게 설계되어 있다.
그렇지만 결과도출에 시간제한을 걸어 버린다면, for문으로 해결할 수 없게된다.

그럼 처음으로 돌아가서 문제를 다시 확인 해 보자.
N을 켜고 끄려면 N만큼 i의 회수를 증가하면서 켜고 끄는동작을 반복한다. 즉 1 <= i <= N 이라는 결과가 성립하게 되는데.
나누어서 떨어지는 숫자라는 것은. 약수를 말한다. 다른 모든 약수를 제외하면 그 어떤 정수이건 간에 1과 자기 자신은 약수로 가지게 된다.
그렇다면 첫번째 지나갈때와 N번째 지나갈때는 무조건 한번씩 켜고, 끄게 되므로 최종적으로는 꺼져 있게 된다. 결국 변화가 없다는 이야기다.

문제를 조금 더 좁혀 보면, 1과 자기자신을 제외하고 약수가 없다면(정수의 범위 내에서) 이 전구는 결국 꺼져 있게 된다.
그럼 약수를 구해야 할까? 아니다. 조금 더 문제를 좁혀 보자.

9의 제곱근은 -3과 3이다. 즉 -3과 3을 제곱하면 9가 된다는 소리다.
여기서 1과 N사이의 범위에 포함되는 것은 3 하나 뿐이다.
9의 약수는 (1, 3, 9) 3개가 존재한다. 좀 전에 말했듯이 1과 자기자신을 제외하면 3이 남는다.
이것이 무슨말인고 하니, 정수의 제곱근을 가지는 정수 N의 약수는 홀수라는 소리다. 즉 불이 켜진다.
정수를 제곱근으로 가지지 않는 N을 하나 예를 들어보자.
약수를 순서대로 나열하면, 제곱근을 가운데로 두고 양쪽에 짝수개의 약수가 배열된다.
정리를 하자면, 양수의 정수를 제곱근으로 가지는 정수 N이 있다면, N의 약수는 홀수개 이다.
11, 8, 13 과 같이 정수를 제곱근으로 가지지 않는 정수는 1과 자기자신을 제외한 약수가 없거나, 있다해도 제곱근이 없으므로 짝수가 된다. 즉 불이 꺼진다.

즉, N을 입력받아 양의 제곱근이 있는지 판단하여, 있다면 전구가 켜져있는 것이고, 아니라면 꺼진 것이다.

#include <stdio.h>
#include <math.h>

int main()
{
long unsigned double cN=0, cTrue = 0;

while (1)
{
scanf("%Lf",&cN);

if ( cN == 0 )
return 0;

cTrue = sqrt(cN); //제곱근 구하기

if ( cTrue * cTrue != cN ) //다시 제곱하여 그 숫자와 일치하는지
printf("N\n");
else
printf("Y\n");
}
}

'프로그래밍' 카테고리의 다른 글

GetTickCount() Function  (1) 2006.01.16
chaos in FOR loop  (0) 2006.01.13
ACM 100 3n+1 Problem  (2) 2006.01.10
오각수 구하기  (0) 2006.01.10
Merge Sorting Algorithm.  (0) 2006.01.10

The Original : http://acm.uva.es/p/v1/100.html
UVA no : 100

영어로 되어있어서 어려운 건줄 알았더니..OTL.. 어쨌든 Accepted!!

>>Background
Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is not known for all possible inputs.

>>The Problem
Given the input 22, the following sequence of numbers will be printed
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 < n < 1,000,000 (and, in fact, for many more numbers than this.)
Given an input n, it is possible to determine the number of numbers printed (including the 1). For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16.
For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j.

>>The Input
The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0.
You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.
You can assume that no opperation overflows a 32-bit integer.

>>The Output
For each pair of input integers i and j you should output i, j, and the maximum cycle length for integers between and including i and j. These three numbers should be separated by at least one space with all three numbers on one line and with one line of output for each line of input. The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line).

>>Sample Input
1 10
100 200
201 210
900 1000

>>Sample Output
1 10 20
100 200 125
201 210 89
900 1000



#include <stdio.h>
#include <stdlib.h>

int solve(int first, int last)
{
int cnt, i = 0;
int max = 1;

for (first; first <= last; first++)
{
i = first;
while (i != 1)
{
if (i % 2 == 0) //even number
{
i = i / 2;
cnt++;
}

else //odd number
{
i = i * 3 + 1;
cnt++;
}
}
if (cnt > max) //MAX Update
max = cnt;
cnt = 0; //cnt Initialize
}
return max;
}

void main(void)
{
int i, j;
scanf("%d %d", &i, &j);

if(i < 1 || i > 10000000 || j < 1 || j > 10000000)
exit(1); //Error Check

int max = solve(i, j); //call solve function

printf("\n%d %d %d\n\n", i, j, max);
}

'프로그래밍' 카테고리의 다른 글

chaos in FOR loop  (0) 2006.01.13
ACM 10110 Light, More Light  (0) 2006.01.13
오각수 구하기  (0) 2006.01.10
Merge Sorting Algorithm.  (0) 2006.01.10
Distribution Counting(분포수 세기)  (0) 2006.01.09

다각형의 모양으로 배열되는 점의 수를 삼각수, 사각수, 오각수라 한다. 입력받은 숫자가 오각수 인지 여부를 판별하는 프로그램을 작성하시오.

삼각수
N개의 점을 연결하여, 삼각형을 만들 수 있다면, N은 삼각수라 한다.
  ㅇ
N=3, 3은 삼각수이다. 3보다 큰 최소의 삼각수는 6이다.

사각수
N개의 점을 연결하여, 사각형을 만들 수 있다면, N은 사각수라 한다.
ㅇ ㅇ
ㅇ ㅇ N=4, 4는 사각수이다. 4보다 큰 최소의 사각수는 9이다.

오각수
N개의 점을 연결하여, 오각형을 만들 수 있다면, N은 오각수라 한다.
N=5, 12, N은 오각수이다.

입력받은 숫자가 오각수인지 아닌지를 판별하는 프로그램을 작성하시오.

#include <stdio.h>

char distinction(int n)
{
int pentagon, mid_n = 0;

for(int i = 2; i < n; i++)
{
for(int j = 1; j < i; j++)
mid_n += j;

pentagon = (i * i) + mid_n; //make pentagon series.

if(n == pentagon) //comparison.
return 'Y';

pentagon, mid_n = 0; //ReInitialize
}
return 'N'; //not find
}

void main(void)
{
int n;
scanf("%d", &n);

char result = distinction(n);

printf("\n%d %c\n\n", n, result);
}

'프로그래밍' 카테고리의 다른 글

ACM 10110 Light, More Light  (0) 2006.01.13
ACM 100 3n+1 Problem  (2) 2006.01.10
Merge Sorting Algorithm.  (0) 2006.01.10
Distribution Counting(분포수 세기)  (0) 2006.01.09
Shell Sort Algorithm.  (0) 2006.01.09

1. 병합정렬은 이미 정렬된 두 파일을 병합(Merge)하는 과정을 일반화한 것이다. 또한 자료 배열에 접근하는 방법이 순차적(Sequential)이다. 다른 정렬 방법이 뚝 떨어진 배열 요소를 비교하고 교환하는데 비하여 병합정렬은 배열을 차례로 읽으면서 비교하는 방법이다.
그래서 병합정렬은 연결 리스트와 같은 순차적 접근만이 가능한 자료 구조에 유일한 정렬방법이 된다.

2. 두 개의 배열에서 꺼내어지는 최소의 값들을 비교하여 작은 쪽의 값을 선택하는 방법으로 이루어진다. 또한 병합에서는 반드시 한 쪽이 먼저 소진되는 경우가 발생하므로 이에 대한 대비도 있어야 한다.

void merge_sort(int a[], int n)
{
int i, j, k, first, second, size;
int *b;

b = new int[n]; //병합 장소

for (size = 1; size < n; size++)
{
first = -2 * size; //first와 second의 초기값
second = first + size;

while (second + size * 2 < n) //다음 second값이 n보다 작으면
{
first = second + size;
second = first + size;

i = first;
j = second;
k = first;

while (i < first + size || (j < second + size && j < n))
{ //병합이 완료되지 않았다면
if (a[i] <= a[j])
{
if (i < first+size)
b[k++] = a[i++];
else
b[k++] = a[j++];
}
else
{
if (j < second + size && j < n)
b[k++] = a[j++];
else
b[k++] = a[i++];
}
}
}
for (i = 0; i < n; i++)
a[i] = b[i];
}
delete b;
}

3. 병합정렬의 루프와 쉘 정렬의 루프는 상당히 비슷하다. 쉘 정렬h를 점점 감소시킴에 반해병합정렬단위의 크기를 증가시켜야 하는 점이 다르지만 루프의 조건이 상당히 비슷하다.

4. 소스를 보면 알겠지만, 루프문의 중복 사용으로 size를 하나씩 증가시키는데, size만큼 블럭을 이동해야 하므로 '*'연산을 하여 1,2,4,8,16... 순서로 블럭을 이동한다., 이전 블럭은 이미 정렬이 이루어진 상태이므로 각 블럭의 최초값부터 하나씩 비교하면서 작은 값을 선택하여 새로운 배열에 삽입한다.
중요한 점은, 1 5 8 11 이라는 A배열13 15 18 19 라는 B배열이 있다고 가정했을때, A배열의 모든 원소는 B배열의 첫번째 원소인 13보다 작다. 그러므로 A배열의 모든 원소가 소진될 때 까지 B배열의 값은 하나도 선택되지 않는다. 그러므로 루프문 내의 조건에서 둘 중 하나의 원소가 바닥났을 때의 경우를 생각하여, 비교할 원소가 없을 때에는 남은 원소를 차례로 선택하도록 해 주는 작업이 필요하다.

'프로그래밍' 카테고리의 다른 글

ACM 100 3n+1 Problem  (2) 2006.01.10
오각수 구하기  (0) 2006.01.10
Distribution Counting(분포수 세기)  (0) 2006.01.09
Shell Sort Algorithm.  (0) 2006.01.09
Indirect Insert Sorting Algorithm  (0) 2006.01.09

1. 같은 키가 많이 있는 배열에 한해 적용할 수 있는 정렬 알고리즘.
1. 특정 키값이 출현하는 빈도를 저장하여 누적분포를 이용하여 간단하게 정렬하는 방법.

2. 다음과 같이 키값이 1에서 5까지만의 정수값을 가지는 a[]배열.
1 3 2 2 3 1 3 2 4 2 4 3 1 2 1 2 5 1 5 3

우선 count[]라는 배열에 각 숫자별로 몇번이나 출현하였는지 카운트 하여 저장한다.
count[1] = 5
count[2] = 6
count[3] = 5
count[4] = 2
count[5] = 2

3. 이 다음의 과정은 count[] 배열의 누적돗수를 구하는 것이다.
count[1] = 5
count[2] = count[2] + count[1] = 11
count[3] = count[3] + count[2] = 16
count[4] = count[4] + count[3] = 18
count[5] = count[5] + count[4] = 20

누적돗수의 의미는 정렬이 완료된 상태에서 1이라는 키는 0에서 4까지 차지하며, 2라는 키는 5부터 10까지, 3이라는 키는 11부터 15까지, 4라는 키는 16부터 17까지, 5라는 키는 18부터 19까지 차지한다는 것. 즉, count[i]는 i라는 키가 위치할 곳을 가리키고 있는 것.

void dist_count(int a[], int n, int m)
{
int i;
int *b, *count;

b = new int[];
count = new int[];

for(i = 0; i <= m; i++) //count배열 초기화
count[i] = 0;

for(i = 0; i < n; i++) //빈도수 계산
count[a[i]]++;

for(i = 2; i <=m; i++) //누적 분포 계산
count[i] = count[i - 1] + count[i];

for(i = n - 1; i >= 0; i--) //뒤에서부터 읽어 b에 저장
b[--count[a[i]]] = a[i];

for(i = 0; i < n; i++) //b에서 a로 복제
a[i] = b[i];

delete b; //메모리에서 해제
delete count;
}

4. 분포수세기는 한정된 용도에서만 적합하다. 약 N번의 비교와 1번의 전체복사가 있는 정도여서 속도가 빠른 편이지만 키 값의 분포를 저장하는 count배열과 작업결과를 임시로 저장할 b배열을 생성해야 하므로 메모리의 소모가 크다. 배열의 크기가 커지면 그만큼 N이 커지므로 메모리는 더 많이 필요하게 된다.

※ 분포수세기 알고리즘은 기수 정렬 알고리즘의 기초가 된다

'프로그래밍' 카테고리의 다른 글

오각수 구하기  (0) 2006.01.10
Merge Sorting Algorithm.  (0) 2006.01.10
Shell Sort Algorithm.  (0) 2006.01.09
Indirect Insert Sorting Algorithm  (0) 2006.01.09
Insertion Sorting Algorithm.  (0) 2006.01.09

1. 삽입정렬의 단점을 개선한 알고리즘 (Shell Sort)

1.1. 삽입정렬의 단점
: 이미 정렬된 배열이나 대충 정렬된 배열에 대해서는 매우 뛰어난 성능을 보이나, 그렇지 않은 경우에는 매우 느린 속도를 보인다. 이는 바로 인접한 요소와 비교를 하기 때문이다. 그래서 만약 역순 배열의 경우 제일 작은 키값이 제일 뒤에 있으므로 N번의 비교와 이동이 필요.

1.2. 개선책
: 'h'만큼의 간격'으로 떨어진 레코드를 삽입 정렬하는 방법.

void shell_sort(int a[], int n)
{
int i, j, k, h, v;

for (h = n / 2; h > 0; h /= 2;) // h <- h/2
{
for (i = 0; i < h; i++) //변이
{
for (j = i + h; j < n; j += h)
{
v = a[j];
k = j;

while(k > h-1 && a[k-h] > v)
{
a[k] = a[k-1]; //이동
k -= h;
}
a[k] = v; //삽입
}
}
}
}

2. 예를 들어 h가 10이라면 0,10,20,30,40...의 요소간의 삽입정렬을 하고 1씩 더한 1,11,21,31,41...의 요소간의 삽입정렬을 하는 식으로 h까지 i를 1씩 증가시키면서 h에 더하여 정렬하기를 반복한다.
정렬이 끝나면 h를 반으로 나누어 또다시 위의 과정을 반복하고,
h가 1이 되면 이미 배열은 거의 다 정렬되어 있는 상태여서 매우 빠른 속도로 삽입 정렬이 가능하다.

3. 입력 자료의 형태에 별로 상관없이 뛰어난 속도를 보인다. 최악의 자료배열인 역순 배열일 경우에도 그다지 큰 차이를 보이지 않는다.
실제로 가장 빠르다는 퀵소트의 경우 20,000개 정도의 정수를 정렬하기에는 힘이 든다.(내부 스택을 사용하는 재귀호출을 사용하므로, 메모리가 부족하기 때문) 하지만, 쉘 정렬은 추가로 메모리가 필요하지 않다는 장점.

4. 하지만, 또다시 개선하여 더욱 우수한 알고리즘을 만들 수 있다.
쉘정렬의 성능은 'h의 설정'에 따라 달라지는데, Robert Sedgewick의 연구결과 최선의 h 수열이 밝혀졌다.
h(n) = 3 * h(n-1) + 1, h(1) = 1 //괄호안의 n은 배열의 길이
즉, 1, 4, 13, 40, 121, 364, 1093

위 함수의 h를 설정하는 부분의 for문을 다음으로 대체하면, 그 성능은 눈에띄게 좋아진다.
for (h = 1; h < n; h = 3 * h + 1)

'프로그래밍' 카테고리의 다른 글

Merge Sorting Algorithm.  (0) 2006.01.10
Distribution Counting(분포수 세기)  (0) 2006.01.09
Indirect Insert Sorting Algorithm  (0) 2006.01.09
Insertion Sorting Algorithm.  (0) 2006.01.09
아파트 단지 번호 붙이기  (0) 2006.01.07

1. 간접 정렬이란 본래 레코드의 배열은 전혀 손대지 않고,
따로 만든 인덱스(index)의 배열을 조작하는 방법.

void inderect_insert_sort(int a[], int index[], int n)
{
int i, j, t;

for (i = 0; i < n; i++) //인덱스 배열 초기화
index[i] = i;
for (i = 1; i < n; i++) //삽입정렬
{
t = index[i];
j = i;

while (a[index[j-1]] > a[t] && j > 0) //삽입위치 찾음
{
index[j] = index[j-1] //인덱스 배열 조정
j--;
}
index[j] = t; //삽입
}
}

2. indirect_insert_sort()는 비교를 위해서는 a배열을 사용하지만, while 루프 내의 실제 교환 작업은 index배열을 사용한다.
이렇게 간접정렬을 하고 나면 실제로 a배열에는 아무 변동이 없다. 그러나 그 정렬된 순서는 index배열에 저장되어 있다.

3. 정렬된 상태라고 가정하고, 제일 첫번째 레코드가 무엇인지 알고자 한다면, a[index[0]]와 같이 하면 되고, i번째 레코드가 무엇인지 알려면 a[index[i]]와 같이 간접적으로 접근한다.

'프로그래밍' 카테고리의 다른 글

Distribution Counting(분포수 세기)  (0) 2006.01.09
Shell Sort Algorithm.  (0) 2006.01.09
Insertion Sorting Algorithm.  (0) 2006.01.09
아파트 단지 번호 붙이기  (0) 2006.01.07
ACM 로마숫자 문제 변형판  (0) 2006.01.07

1. 선택정렬과 함께 가장 많이 사용되는 정렬방식으로 선택정렬이 많은 비교와 적은 교환으로 특정 지워진다면, 삽입정렬은 반대로 적은 비교와 많은 교환으로 특정 지워진다.

2. 이미 정렬이 된 부분에 새로운 키를 적절한 장소에 삽입하는 동작을 반복적 수행.

3. i, j를 셋팅하고, i변수는 배열을 순서대로 카운트 한다. j변수는 i-1로 초기셋팅이 되어 i변수를 뒤에서 쫓아간다. i와 j변수가 각각 가리키고 있는 배열값을 비교하여 뒤에 있는 j변수 배열값이 i변수 배열값보다 크다면 i변수 배열값을 우측으로 옮기고, j값을 감소시킨다. while문을 사용하여 더이상 비교할 값이 없을때까지 비교하여, 모두 우측으로 이동하고 남는 자리에 처음에 비교대상이 되었던 값을 삽입하는 동작을 반복한다.

void insert_sort(int a[], int n)
{
int t, j;

for(int i=1; i<n; i++)
{
t = a[i];
j = i;

while(a[j-1] > t && j > 0)
{
a[j] = a[j-1];
j--;
}
a[j] = t;
}
}

삽입정렬은 입력자료에 굉장히 민감하다. 입력자료의 정렬된 정도에 따라 효율이 좋을 수도 있고 안 좋을 수도 있다.
그러나 삽입 정렬의 경우 작은 크기의 대충 정렬된 배열에 대해서는 제일의선택이 된다.

알고리즘을 개선하는 것은 어렵지 않다.
만약, 삽입 정렬할 레코드의 키값이 일정한 범위 내에 있다면 아래 기법을 고려해 볼 만 하다. 예를 들어 키값이 정수값인데 양의 정수만 다룬다면 이 배열의 제일 첫 요소 a[0]에 -1과 같은 값을 집어넣는다.
그리고, 실제의 자료들은 a[1] 이후에 저장하도록 한다.

그렇다면 다음의 insert_sort_1()함수와 같이 while루프의 판단문에서 j > 0과 같은 비교문을 하나 없앨 수 있다.

void insert_sort_1(int a[], int n)
{
int j, t;
for (i = 2; i<=n; i++)
{
t = a[2];
j = i;
while (a[j-1] > t) // j > 0이 없어졌다.
{
a[j] = a[j-1];
j--;
}
a[j] = t;
}
}

j > 0 이 없어진 것과 i의 변동 범위가 달라진 것 외에는 초기 함수와 다른 것이 없다.
a[0]는 루프의 경계를 벗어남을 방지하는 보초(sentinel)이다. a[0]에는 -1이 들어있고, 배열에는 양의 정수만 들어 있으므로, 예를 들어 가장 작은 수 1이 삽입될 곳을 찾기 위해 j값이 줄어든다 해도 a[0]의 값 -1보다는 1이 크므로 -1 뒤에 1이 삽입된다.

이렇게 a[0]는 경계의 벗어남을 막아주며, 또한 j > 0와 같은 비교문을 하나 없앰으로 인하여 N이 클 경우 이 기법의 효과는 두드러진다.

'프로그래밍' 카테고리의 다른 글

Shell Sort Algorithm.  (0) 2006.01.09
Indirect Insert Sorting Algorithm  (0) 2006.01.09
아파트 단지 번호 붙이기  (0) 2006.01.07
ACM 로마숫자 문제 변형판  (0) 2006.01.07
초점의 원리  (0) 2006.01.06