ANMIAN

1. 삽입정렬(Insert Sort)이란?

-. 가장 왼쪽에 있는 첫번째 값을 이미 정렬된 상태로 가정하고 나머지 자료들을 정렬한다.

-. 두번째 값을 기준으로 첫번째 값을 비교하여 값에 따라 순서대로 나열하며, 세번째 값을

   기준으로 두번째 값과 첫번째 값을 비교하여 값에 따라 순서대로 나열한다.

   위와 같은 방법으로 n - 1개의 값과 비교하여 삽입될 적당한 위치를 찾아 삽입한다.

-. 이미 정렬이 된 부분에 새로운 값을 적절한 순서에 삽입하는 동작을 반복적으로 하는 정렬이다.

-. 적은 비교와 많은 교환이 필요한 방법이므로 소량의 자료를 처리하는데 가장 유리한다.

2. 삽입정렬을 이용하여 오름차순으로 정렬하는 방법

3. 삽입정렬의 비교회수

-. 최선일 경우의 비교회수 공식 : N - 1

-. 최악일 경우의 비교회수 공식 : N(N – 1)/2

-. 위의 그림을 보시면 아시겠지만 제일 처음에는 (N – 1)번을 비교하고,

   그 다음에는 (N – 2)번 만큼 비교하고, 그 다음은 (N – 3)번을 비교하면서 비교회수가 1이 될

   때까지 이 작업을 반복할 것이다.

-. 비교회수는 (N – 1) + (N – 2) + (N – 3) …… + 1 이 될 것이다.

   최대 (N – 1)번을 수행할 것이며, 각 패스가 수행할 때마다

   수학식으로 표현하면    이므로 공식은 N(N – 1)/2 이런 공식이 성립된다.

-. 5개의 값을 오름차순으로 선택정렬을 하면

   공식에 의해서 5(5 – 1)/2 = 10 가 성립된다.

   즉, 총 10번의 비교를 통해서 오름차순으로 정렬된 값을 볼 수 있다.

4. 삽입정렬의 연산시간

   -. 연산시간 공식 : O(n²)

-. 연산시간을 표기하는 방법은 일반적으로 사용하는 O표기법인데, 이 O표기법은 ‘최악의 경우’

   (Worst Case)에 대한 연산시간을 나타낸다.

-. 수학식으로 표현하면 아래와 같다.

     = n(n – 1) – (n – 1)/2 = n(n - 1)/2 이므로 Worst Case는 n(n – 1)/2 이다.

   그래서 연산시간은 O(n²)가 되는 것이다.

5. 삽입정렬의 장점

-. 정렬된 값은 교환이 한번도 일어나지 않고 비교만 n- 1번 하게 된다. (그래서 속도가 빠르다.)

6. 삽입정렬의 단점

-. 입력자료(정렬되어 있는 자료인지 아니면 역순의 자료인지)에 민감하다.

-. 역순일 때는 교환과 비교의 회수가 N(N – 1)/2번이 되는 최악의 경우이므로 선택정렬보다

   속도가 떨어진다.

7. 삽입정렬을 이용해서 작성한 예제

결과는 아래와 같습니다.

1. 힙정렬(Heap Sort)이란?

-. 힙은 전이진 트리에서 임의의 노드는 언제나 자식노드들 보다 큰 값을 갖는 구조이다.

-. 여러 개의 노드들 중에서 가장 큰 키값을 가지는 노드나 가장 작은 키값을 가지는 노드를

   빨리 찾아내도록 만들어진 자료구조이다.

-. 완전 이진 트리의 하나로서 각각의 노드는 유일한 키값을 가진다.

-. 트리구조에서는 Root가 가장 큰 값을 보유하고 있다.

-. 우선순위 큐의 일종으로 우선순위가 높은 요소를 효율적으로 선택할 수 있는 자료구조이다.

2. 우선순위 큐(Priority Queue)란?

-. 큐에 저장된 자료는 순위에 의해 순서가 유지되는 자료구조의 추상적인 개념이며 다음

   일곱가지의 동작이 정의되는 경우가 대부분이다.

   1) 생성(Construct) – 주어진 N개의 자료로 우선순위 큐를 생성한다.

   2) 삽입(Insert) ---- 우선순위 큐에 새로운 자료를 삽입한다.

   3) 제거(Remove) ---- 순위가 가장 높은 자료를 제거한다.

   4) 대치(Replace) --- 순위가 가장 높은 자료와 새로운 자료를 대치한다.

   5) 변경(Change) ---- 자료의 순위를 변경한다.

   6) 삭제(Delete) ---- 임의의 자료를 삭제한다.

   7) 결합(Join) ------ 두 우선순위 큐를 결합하여 큰 우선순위 큐를 만든다.

3. 힙정렬을 이용하여 오름차순으로 정렬하는 방법

4. 힙정렬의 비교회수

-. 비교회수 공식 : 2N log N

5. 힙정렬의 연산시간

  -. 연산시간 공식(평균) : 0(n log n)

-. 연산시간을 표기하는 방법은 일반적으로 사용하는 O표기법인데, 이 O표기법은 ‘최악의 경우’

   (Worst Case)에 대한 연산시간을 나타낸다.

6. 힙정렬의 장점

-. 다른 정렬들에 비해 최악의 연산시간일 경우에도 0(n log n)으로 적게 든다.

-. 추가적인 메모리를 필요로 하지 않는다.

7. 힙정렬의 단점

-. 데이터 구조에 따라서 다른 정렬보다 조금 늦게 정렬될 수도 있다.

8. 힙정렬을 이용해서 작성한 예제

1. 쉘정렬(Shell Sort)이란?

-. 자료를 여러 부분으로 분할하여 적절한 크기로 나누어진 배열들을 간단한 삽입정렬 등을 이용

   하여 정렬한 후 합쳐가면서 다시 정렬하는 방식이다.

   결국, 전체를 정렬하는 방식이며 자료들을 분할하는데 있었어 너무 잘게 분할하거나 너무

   엉성하게 분할하면 부분 정렬 후 병합의 어려움이 생길 수 있다.

   (적당한 매개변수(h)를 정하고 h만큼 떨어져 있는 값을 비교하여 h가 1이 될 때까지 반복)

-. 멀리 떨어진 자료와 비교할 때 멀리 떨어져 있는 값들만 비교하고 떨어진 정도를 점차 줄여나

   가다가 마지막에 1이 되면 정렬이 완료된다.

2. 쉘정렬에서 자료를 분할하는 평균적인(자주 사용하는) 공식

-. 자료를 몇 개로 분할해야 되는지의 기준(increments 또는 h-sequence라고 부른다)이 전체적인

   성능에 결정적인 영향을 미친다.

   (일반적으로 떨어진 정도를 구하는 것은 여러 가지 방법이 있으며 경우에 맞게 정하면 된다.)

-. 평균적인 공식

     h(1) = 1;

     h(i + 1) = 3 * h(i) + 1;

   로 하면 좋은 결과를 얻을 수 있으며, 이 순열은 1, 4, 13, 40 …의 역순으로 된 순열이다.

   만약, 배열의 크기가 60일 때는 먼저 40개의 부분배열로 나누어 삽입정렬을 이용하고,

   13개의 부분배열로 나누어서 삽입정렬을 이용한다.

   배열을 다시 4개의 부분배열로 나누어 삽입정렬을 한 후 마지막으로 배열전체에 삽입정렬을

   한다.

3. 쉘정렬을 이용하여 오름차순으로 정렬하는 방법

4. 쉘정렬의 비교회수

-. 순열 h가 1, 4, 13, 40 … 일 때의 비교회수

5. 쉘정렬의 연산시간

  -. 연산시간 공식 : O(n²)

-. 연산시간을 표기하는 방법은 일반적으로 사용하는 O표기법인데, 이 O표기법은 ‘최악의 경우’

   (Worst Case)에 대한 연산시간을 나타낸다.

-. 수학식으로 표현하면 아래와 같다.

     = n(n – 1) – (n – 1)/2 = n(n - 1)/2 이므로 Worst Case는 n(n – 1)/2 이다.

   그래서 연산시간은 O(n²)가 되는 것이다.

6. 쉘정렬의 장점

-. 입력자료에 상관없이 뛰어난 속도를 보인다.

-. 삽입정렬은 왼쪽에 있는 자료가 정렬이 되었다는 가정하에 정렬을 하므로, 가장 오른쪽에 있는

   자료를 왼쪽으로 삽입하려고 하면 많은 교환이 이루어지는 단점을 보완한 정렬방식이다.

-. 멀리 떨어져있는 자료들이 비교 및 교환될 수 있으므로 어떤 자료가 제 위치에서 멀리 떨어져

   있다면 여러 번의 교환이 발생하는 버블정렬 방식의 단점을 해결한다.

7. 쉘정렬의 단점

-. 기준(h)을 정하는 방법에 따라 알고리즘의 성능이 달라진다.

-. 안정성이 없다.

8. 쉘정렬을 이용해서 작성한 예제

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

int IsPerfectSquareNumber(unsigned long number);
int IsPrime(unsigned long number);

int main(void)
{
        unsigned long number;

        printf("자연수 하나를 입력하십시오 : ");
        scanf("%lu", &number);
        printf("%lu는 완전제곱수%s니다.\n", number, IsPerfectSquareNumber(number)?" 입":"가 아닙");
        return 0;
}

int IsPerfectSquareNumber(unsigned long number)
{
        unsigned long i, j;

        for(i=2; i<=number; i++)
        {
                if(IsPrime(i))
                {
                        for(j = 0; (number%i)==0; j++)
                                number/=i;
                        if((j % 2) != 0)
                                return 0;
                }
        }
        return 1;
}

int IsPrime(unsigned long number)
{
        unsigned long i, sqrt_number;

        if(number < 2)
                return 0;
        sqrt_number = (unsigned long)sqrt(number);
        for(i=2; i<=sqrt_number; i++)
                if(number%i == 0)
                        return 0;
        return 1;
}

IsPrime함수의 사용이다. IsPerfectSquareNumber함수 내에서 for문을 돌면서 2부터 1씩 증가시키는 값으로 나누어질수 있는만큼 계속 나누어간다. 소인수분해는 소수(Prime number)로 나누어야 한다. 그런데 2로 나눈 나머지가 다시 2로 나누어지면 반복해서 나누는 과정이 있다.
                        for(j = 0; (number%i)==0; j++)
                                number/=i;
이 부분이다. 이 구문을 만나면 소수가 아닌 숫자로는 for문의 판별식((number%i)==0)을 만족할 수 없으므로 애초에 for문에 들어가지 못한다.
예를 들어 8로 나누어지는 수라면 이미 2로 3번 나누었다. 6으로 나누어지는 수라면 2에서 한번 3에서 한번 나누었으므로 i가 6까지 왔으면 당연히 나눌수 없게된다.

#include <stdio.h>
#include <math.h>
int IsPerfectSquareNumber(unsigned long number);

int main(void)
{
        unsigned long number;
        printf("자연수 하나를 입력하십시오 : ");
        scanf("%lu", &number);
        printf("%lu는 완전제곱수%s니다.\n", number, IsPerfectSquareNumber(number)?" 입":"가 아닙");
        return 0;
}
int IsPerfectSquareNumber(unsigned long number)
{
        unsigned long i, j;
        for(i=2; i<=number; i++)
        {
            for(j = 0; (number%i)==0; j++)
                    number/=i;
            if((j % 2) != 0)
                    return 0;
        }
        return 1;
}

여기서 if문은 어떤 수가 되건 어떠한 값(소수가 아니더라도)의 제곱이 되면 완전제곱이므로 같은 수가 쌍으로 있으면 완전제곱이 될 수 있다는 생각이다. 예를 들어 144(= 12*12)는 2*2*2*2*3*3이므로 2^4*3^2으로 표현된다. 2가 두쌍 3이 한쌍 있으므로 완전제곱이 된다.

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

int IsPerfectSquareNumber(unsigned long number);

int main(void)
{
        unsigned long number;
        printf("자연수 하나를 입력하십시오 : ");
        scanf("%lu", &number);
        printf("%lu는 완전제곱수%s니다.\n", number, IsPerfectSquareNumber(number)?" 입":"가 아닙");
        return 0;
}

int IsPerfectSquareNumber(unsigned long number)
{
       unsigned long ga = (unsigned long )sqrt(number); //ga == geometric_average
       return ((ga * ga) == number);
}

기하평균을 정수로 변환시킨 후 다시 제곱하여 원래의 수가 나오는지 확인하는 것이다.
만약 기하평균이 정수가 아니라면 slicing이 발생하여 소수점 아래는 버린다. 그러면 제곱을 해도 원래의 값이 되지 않는다. 형 변환의 위험을 역이용하였다. 위험한거 아냐?라고 생각한다면 큰 오해다. 마지막 소스는 수학적으로 문제가 없으며 처음보다 훨씬 안전한 소스라고 생각한다.

int a = 10;
 printf("+10 : %d\n", +10);      
 printf("-10 : %d\n", -10);  
 printf("+a : %d\n", +a);    
 printf("-a : %d\n", -a);  
 printf("++a : %d\n", ++a);
 a = 10;
 printf("a++ : %d\n", a++);
 printf("a : %d\n", a);
 a = 10;
 printf("--a : %d\n", --a);
 a = 10;
 printf("a-- : %d\n", a--);

출력 결과를 예상해보고 확인해보라.

   0011 1000 0111                 0010 1000 0111
 & 0101 0000 1111              | 0101 0000 1111              ! 0101 0000 1111
=============================================================================
    0001 0000 0111                0111 1000 1111                1010 1111 0000