Sort.. algorithm

<5. 정렬 알고리즘(1) >

1) 개요
     * 정렬(sort) : 임의위 순서대로 배열하는 것
     *오름차순(ascending order)
     *내림차순(descending order)

     1] 정렬의 방법론
          * 파일(file) - 정렬대상, 정보의 단위인 레코드의 나열
          * 필드(field) - 각 레코드의 구체적 정보단위
          * 레코드(record)는 C에서 구조체로 표현, 필드는 구조체의 멤버!
          * 키(key) - 필드 중에서 비교의 대상인 것

     2] 정렬 알고리즘의 다양성
          * 간단 : 선택정렬, 삽입정렬, 거품정렬, 셀정렬
          * 복잡 : 퀵정렬, 기수정렬, 힙정렬, 병합정렬

          *내부정렬 (Internal sort) - 속도 빠름, 모든자료를 메인메모리로 옮겨 놓아야 하는 부담
          *외부정렬 (External sort) - 속도 느림, 자료가 메인메모리 차지안하므로 메모리 절약!

          *직접정렬 (Direct sort) - 메모리 절약 but 속도느림
          *간접정렬 (Indirect sort) - 메모리 소요, 실제 레코드 교환안하므로 속도 빠름

          * 삽입(Insertion) : ex) 삽입정렬
          * 교환(Exchange) : ex) 거품정렬, 퀵정렬, 기수교환정렬
          * 병합(Merging) :  ex) 병합정렬
          * 선택(Selection) : ex)선택정렬, 힙정렬
          * 세기(Counting) : ex) 분포수세기, 직접기수정렬

--------------------------------------------------------------------------------

2) 선택정렬 (Selection sort)

          (1) i=0;
          (2) i=n-1면 끝
          (3) i~n-1 중 최소값을 min에 저장
          (4) i항과 min항을 교환
          (5) i하나 증가 -> 2로~

     void select_sort (int a[], int n)
     {
          int min, minindex, i, j;

          for(i=0; i<n-1; i++)
          {
              minindex=i;
              min=a[i];
               for(j=i+1; j<n; j++)
               {
                    if(min>a[j])
                    {
                         min=a[j];
                         minindex=j;
                    }
               }
               a[minindex] = a[i];
               a[i] = min;
          }
     }

     # 배열 앞부분부터 차례로 정렬해 나간다.
     # 아직 정렬하지 않은 부분은 n의 변함이 없다.
     # 비교횟수 N^2/2정도, 교환횟수<=N (최악의 경우-역순일 때, 교환횟수=N)
     # 성능 O(N^2)
     # 안정성이 없다.
     # N<100에서 만족할 만한 속도~

--------------------------------------------------------------------------------

3) 삽입정렬 (Insertion sort)

     (1) i=1;
     (2) j=i;
     (3) a[j-1]>a[i], j>0인 동안
         a[j]=a[j-1]; j--;
     (4) a[j] = a[i];
     (5) i++, 2로~~ ( → i항 이하는 이미 정렬된 상태가 됨!!!)

     void insert_sort(int a[], int n)
     {
          int i, j, t;
          for(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;
          }
     }

     # 삽입정렬은 입력자료에 민감
     # 이미 정렬된 배열일 경우 매우 빠름
     # 최악의 경우 : 역순!
     # 난수 배열인 경우 - 선택정렬보다 효율이 좋다
     # O(N^2)의 성능

--------------------------------------------------------------------------------

4) 거품정렬 (Bubble Sort)

     (1) i=0;
     (2) i=n-1되면 끝
     (3) j=1;
     (4) j=n-1면 7로
     (5) a[j-1]>a[j] 이면 두 값을 교환
     (6) j하나 증가 -> 4로
     (7) i증가, 2로!

     void bubble_sort(int a[], int n)
     {
          int i, j, t;
          for(i=0; i<n-1; i++)
         {
               for(j=1; j<n-1; j++)
               {
                    if(a[j-1]>a[j])
                    {
                         t=a[j-1];
                         a[j-1]=a[j];
                         a[j]=t;
                    }
               }
          }
     }

     # 최선의 경우 - 이미 정렬된 배열
     # 최악의 경우 - 역순!
    

--------------------------------------------------------------------------------

5) 쉘 정렬 ( Shell sort )
   -  h간격으로 떨어진 레코드를 삽입정렬 함

    (1)  h의 초기값을 구한다.
    (2)  h가 1보다 작으면 끝낸다
    (3) i=0;
    (4) i 가 h보다 크기가 같으면 7로 간다.
    (5) (h 간격+i)요소들에 대해서 삽입 정렬을 한다.
    (6) i를 하나 증가시키고 4로 간다.
    (7) h의 다음값을 구하고 2로 간다!

    void shell_sort (int a[], int n)
    {
        int i, j, k, h, v, j;
        for(h=0; i<h; i++)
        {
            for(j=i+h; j<n; j+=h)
            {
                v=a[j];
                k=j;

               while(k>h-1 && a[k-1]>v)
                {
                   a[k]=a[k-h];
                    k-=h;
                }
            a[k]=v;
        }
        }
    }

    # 안정성이 없다.
    # 입력자료의 형태에 상관없이 속도  good!!!
    # 최선의 경우 - 이미 정렬된것
    # 최악의 경우 - 난수 (하지만 그래도 빠른편!)
    # O(N(log N^2), O(N^1.25) 의 성능

--------------------------------------------------------------------------------

6) 분포수 세기 (Distribution counting)
        - 같은 키가 많이 있는 배열에 한해 적용할 수 있다.
        - 특정 키 값이 출현 하는 빈도를 저장하여 누적분포를 이용하여 간단하게 정렬

     (1) count[]배열을 O으로 초기화
     (2) a[] 배열의 키의 빈도를 계산하여 그 빈도를 count[]에 저장
     (3) count[]배열을 누적 분포로 변환
     (4) a[]배열을 뒤에서부터 읽어서 b[--count[a[i]]]에 저장

    coid dist_count (int a[], int n, int m)
    {
        int i; int *b, *count;
   
        b=(int*)malloc(sizeof(int)*n);
        count=(int*)malloc(sizeof(int)*(m+1));

        for(i=0; i<=m; i++) 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[--count[a[i]]] = a[i];
        for(i=0; i<n; i++) a[i]=b[i];
        free(b);
        free(count);
    }

--------------------------------------------------------------------------------