정렬 - 삽입정렬(Insert Sort), 힙정렬(Heap Sort), 쉘정렬(Shell Sort)

삽입정렬(Insert Sort)

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. 삽입정렬을 이용해서 작성한 예제

#include "stdio.h"   void Insert_Sort(int parm_data[], int parm_count) {     int i, temp, move_index;     int comparison_count = 0;       for(i = 1; i < parm_count; i++){          temp = parm_data[i];          move_index = i - 1;            comparison_count++;          while(move_index >= 0 && parm_data[move_index] > temp){              parm_data[move_index + 1] = parm_data[move_index];              move_index--;          }          parm_data[move_index + 1] = temp;      }      printf("총 비교회수는 [ %d 회] 이다.", comparison_count);      printf("\n\n\n");   }   void main() {     int array[5] = {7, 4, 11, 9, 2};     int i;       printf("=== 삽입정렬하기 전 ===\n\n");     for(i = 0; i < 5; i++) printf("%d   ", array[i]);     printf("\n\n");     printf("================================");     printf("\n\n");       Insert_Sort(array, 5);     printf("=== 삽입정렬한 후 ===\n\n");     for(i = 0; i < 5; i++) printf("%d   ", array[i]);     printf("\n\n"); }

 

 

결과는 아래와 같습니다.

힙정렬(Heap Sort)
초보 프로그래머의 실력을 보고자 할 때 우선순위 큐를 물어보는 경우가 많다. 실제 기술 면접 때도 우선순위 큐를 다루는 문제가 자주 나오니 확실하게 기억해두자.
우선순위 큐는 힙(Heap)을 사용해야 한다. 물론 삽입정렬과 큐를 사용해도 무관하지만 그것은 O(N^2)알고리즘이다. 이에 반해 Heap은 O(N log N)이다. 엄청난 차이를 보이는 알고리즘.. 그러한 차이를 알고있느냐가 관건인 것이다. 돌아만 가는 코드를 내놓은 프로그래머는 실무에선 그다지 필요하지 않다.

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. 힙정렬을 이용해서 작성한 예제

#include "stdio.h"   void Swap(int *parm_a, int *parm_b) {     int ex = *parm_a;     *parm_a = *parm_b;     *parm_b = ex; }   void Min_Heap(int parm_data[], int parm_start, int parm_count) {     int node_left, node_right, node_current, node_start, node_index;     if(parm_count - parm_start < 2) return;     node_current = parm_start;       while(node_current >= 0){         node_index = node_current;         node_start = node_current;         while(node_start*2+1 < parm_count){             node_left = node_start*2+1;             node_right = node_start*2+2;             node_start = node_left;               if(node_right < parm_count && parm_data[node_right] >= parm_data[node_left]){                 node_start = node_right;             }             if(parm_data[node_start] > parm_data[node_index]){                 Swap(&parm_data[node_index], &parm_data[node_start]);                 node_index = node_start;             }         }         --node_current;     } }   void Heap_Sort(int parm_data[], int parm_count) {     Min_Heap(parm_data, parm_count/2-1, parm_count);     while(parm_count > 0){         --parm_count;         Swap(&parm_data[0], &parm_data[parm_count]);         Min_Heap(parm_data, 0, parm_count);     } }   void main() {     int array[10] = {27, 4, 37, 2, 62, 12, 59, 16, 49, 18};     int i;       printf("=== 힙정렬하기 전 ===\n\n");     for(i = 0; i < 10; i++) printf("%d   ", array[i]);     printf("\n\n");     printf("================================");     printf("\n\n");       Heap_Sort(array, 10);     printf("=== 힙정렬한 후 ===\n\n");     for(i = 0; i < 10; i++) printf("%d   ", array[i]);     printf("\n\n"); }

 

 

결과는 아래와 같습니다.

쉘 정렬(Shell Sort)

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"   // 쉘정렬에서 사용하는 삽입정렬 void Insert_Sort(int parm_start, int parm_interval, int parm_data[], int parm_count) {     int i, j, temp;       for(i = parm_start; i <parm_count; i+= parm_interval){         temp = parm_data[i];         j = i - parm_interval;           while(j >= 0 && parm_data[j] > temp){             parm_data[j + parm_interval] = parm_data[j];               // 떨어진 값만큼 감소시키면서 삽입정렬한다.             j -= parm_interval;         }         parm_data[j + parm_interval] = temp;     } }   void Shell_Sort(int parm_data[], int parm_count) {     // interval은 떨어진 정도의 값, parm_count는 정렬할 데이터의 개수     int interval = parm_count;       do{         interval = interval/3 + 1;         for(int i = 0; i < interval; i++){             Insert_Sort(i, interval, parm_data, parm_count);         }     } while(interval > 1); }   void main() {     int array[10] = {29, 4, 17, 63, 55, 2, 31, 11, 9, 18};     int i;       printf("=== 쉘정렬하기 전 ===\n\n");     for(i = 0; i < 10; i++) printf("%d   ", array[i]);     printf("\n\n");     printf("================================");     printf("\n\n");       Shell_Sort(array, 10);     printf("=== 쉘정렬한 후 ===\n\n");     for(i = 0; i < 10; i++) printf("%d   ", array[i]);     printf("\n\n"); }

 

 

결과는 아래와 같습니다.

출처 : http://www.tipssoft.com
퍼갈때 출처를 달아달라는 말이 있었다..ㅎ