[자료구조]CH9. 정렬(삽입 정렬~기수 정렬)

참조 : C로 배우는 쉬운 자료구조(이지영 저)

공부 날짜 : 21.03.22

 

<Section5> 삽입 정렬

 

1. 삽입 정렬의 이해(Insert Sort)

 

 정렬되어 있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방식으로 정렬을 수행한다. 

삽입 정렬에는 정렬된 앞부분의 원소는 부분 집합 S(Sorted Subset), 

정렬되지 않은 나머지 원소는 부분 집합 U(Unsorted Subset)이 된다. U가 공집합이 되면 삽입 정렬 완성.

 

2. 삽입 정렬 알고리즘

크기가 n인 배열 a[]의 원소를 삽입 정렬

 

 InsertionSort(a[] , n)

    for (i ← 1 ; i < n ; i ← i+1) do {  //초기에 인덱스 0은 부분집합 S에 해당하므로 인덱스 1부터 시작

        temp ← a[i]; 

        j ← i;

 

        if (a[j-1] > temp) then move ← true;//초기a[j-1]은 부분집합 S의 마지막 원소.삽입할 원소보다 더 크면 자리 이동

        else move false; // 삽입할 원소가 더 크면 자리 이동 없음

 

        while (move and j > 0) do {

            a[j] ← a[j-1]; //자리가 더 크면 자리를 한 칸 뒤로 이동

            j ← j-1; //비교할 원소 위치를 왼쪽 이동

        }

 

        a[j] ← temp; //삽입할 원소의 자리 확정

    }

 end insertionSort()

 

<Section6> 셸 정렬

 

1. 셸 정렬의 이해 (Shell Sort)

 

  일정한 간격(interval)으로 떨어져 있는 자료들끼리 부분집합을 구성하고, 각 부분 집합에 있는 원소에 대해 삽입 정렬을 수행하는 작업을 반복하여 전체 원소를 정렬하는 방법이다. 

부분집합으로 나누어 삽입 정렬하면 비교 연산과 자리 이동 연산의 횟수를 줄일 수 있다. 

 

기준이 되는 간격을 매개변수 h에 저장 후, 한 단계가 수행될 때마다 값을 감소시키고 셸 정렬을 순환 호출한다.

h가 1이 될 때까지 반복하면서 정렬한다. 

 

h값은 원소 개수의 1/2을 사용하고 한 단계 수행할 때마다 값을 반으로 감소시킨다.

 

2. 셸 정렬 알고리즘

 

*크기가 n인 배열 a[]의 원소들을 셸 정렬

 shellSort(a[] , n)

     interval ← n; 

     while (interval >= 1) do { //h값이 1이 되기 전까지

         interval ← interval / 2; //한 단계 수행될 때마다 h값을 반으로 감소

         for (i ← 0 ; i < interval ; i ← i+1) do {

             intervalSort(a[] , i , n , interval); //부분집합에서 셸 정렬 순환 반복

         }

     }

 end shellSort()

 

*셸 부분집합에서의 삽입 정렬

 intervalSort(a[] , begin , end , interval)

 for (i ← begin+interval ; i <= end ; i ← i+interval) do { // 부분집합 U에 해당

    item ← a[i];

 

    for (j ← i-interval ; j >= begin and item < a[j] ; j ← j-interval) do // 부분집합 S에 해당

        a[j+interval] ← a[j]; // 원소 값이 더 크면 뒤 순서로 자리 이동

 

    a[j+interval] ← item; // item의 자리 확정

 }

 end intervalSort()

 

<Section7> 병합 정렬

 

1. 병합 정렬의 이해(Merge Sort)

 

 여러 개의 정렬된 자료 집합을 병합하여 하나의 정렬된 집합으로 만드는 정렬 방법이다. 

병합 정렬은 전체 원소에 대해 수행하지 않고 부분 집합으로 분할(Divide)하고,

각 부분 집합에 대해서 정렬 작업을 정복(Conquer)하고 다시 결합(Combine)한다.

 

정렬된 자료 집합 두 개를 결합하여 하나의 집합으로 만드는 병합 방법을 2-way 병합이라 하고,

n개의 정렬된 자료 집합을 결합하여 하나의 집합으로 만드는 병합 방법을 n-way 병합이라고 한다.

 

2. 병합 정렬 알고리즘

 

*크기가 n인 배열 a[]의 원소들을 병합 정렬

 mergeSort(a[] , m , n)

      if (a[m:n]의 원소 수 > 1) then {

          전체 집합을 부분집합 두 개로 분할;

          mergeSort(a[] , m , middle); // 왼쪽 부분집합을 다시 분할

          mergeSort(a[] , middle+1 , n); //오른쪽 부분집합을 분할

          merge(a[m:middle] , a[middle+1:n]); //병합

      }

 end mergeSort()

 

*부분집합의 병합

 merge(a[m:middle] , a[middle+1:n])

     i ← m; // 왼쪽 부분집합의 첫 번째 원소

     j ← middle+1; //오른쪽 부분집합의 첫 번째 원소

     k ← m; //병합 집합의 첫번째 원소

 

     while (i <= middle and j <= n) do {

         if (a[i] <= a[j]) then { //왼쪽 부분 집합의 원소가 오른쪽 부분집합의 원소보다 크면

            sorted[k] ← a[i]; //병합 집합에 왼쪽 부분집합 원소 입력

            i ← i+1; // 왼쪽 부분 집합에서 위치 한 칸 오른쪽으로

         }

         else { //오른쪽 부분 집합의 원소가 왼쪽 부분집합의 원소보다 크면

            sorted[k] ← a[j]; // 병합 집합에 오른쪽 부분집합 원소 입력

            j ← j+1; // 오른쪽 부분집합에서 위치 한 칸 오른쪽으로 

         }

         k ← k+1; //병합 집합 삽입할 원소 위치 한 칸 이동

     }

     if (i > middle) then 두 번째 부분집합에 남아있는 원소를 병합 집합 sorted에 복사;

     else 첫 번째 부분집합에 남아있는 원소를 병합 집합 sorted에 복사;

 end merge()

 

<Section8> 기수 정렬

 

1. 기수 정렬의 이해 (Radix Sort)

 

 분배 방식의 정렬 방법으로 정렬한 원소의 키 값에 해당하는 버킷에 원소를 분배하였다가 버킷의 순서대로 원소를 꺼내는 방법을 사용한다.

 

원소의 키를 표현하는 값의 기수만큼 버킷이 필요하고, 키값의 자리수만큼 기수 정렬을 반복한다. 

 

10진수의 키값을 가진 원소들의 경우는 버킷이 0~9까지 총 10개 있으며,

1의 자리수, 100의 자리수, 100의 자리수 ... 순서로 기수 정렬을 수행한다.

 

선입선출 구조를 사용하므로 큐를 활용한다.

 

2. 기수 정렬 알고리즘

크기가 n인 배열 a[]의 원소들을 기수 정렬

 

 radixSort(a[] , n)

      factor ← 1;

 

      for (k ← 0 ; k < KEY_DIGIT ; k ← k+1) do { // 원소들 중 최대 자리수를 KEY_DIGIT에 준다.

 

          for (i ← 0 ; i < n ; i ← i+1) do {

              enQueue(Q[(a[i]/factor) mod RADIX] , a[i]); // 원소들의 진수를 RADIX에 준다.

          }

 

          p ← -1; //배열a의 인데스를 저장하기 위한 변수

 

          for (i ← 0 ; i < RADIX ; i ← i+1) do {

              while (Q[i] != NULL) do {

                   p ← p+1;

                   a[p] ← deQueue(Q[i]); //큐에서 원소를 삭제하면서 차례대로 배열에 정렬

              }

          }

          factor ← factor*RADIX;

 }

 end radixSort()