[C언어 알고리즘] 2.6.2 쉘 정렬 알고리즘 구현

[C언어 알고리즘] 2.6.2 쉘 정렬 알고리즘 구현

---

쉘 정렬 알고리즘을 구현합시다.

쉘 정렬(base:컬렉션, n:원소 개수, compare:비교 논리)

    반복(step:=size/2;  step>0  ; step:=step/2)

        반복(i:=0; i<step ; i:=i+1)

            삽입정렬2(base+i, size-n, step)

 

삽입정렬2(base:컬렉션, size:원소 개수, step:간견)

    반복(i:=step;  i<size  ; i:= i+step)

        반복(j=i; j>0 ; j:=j-step)

            조건(compare (base [j-step], base [j]) < 0)

                temp: = base [j-step]

                base[j-step] = base [j]

                base[j] = temp

            아니면

                루프 탈출

 

//쉘 정렬(Shell Sort)

#include <stdio.h>

먼저 두 개의 값을 교환하는 매크로 함수를 작성합니다.

#define SWAP(a,b)  {int t; t = a; a=b; b=t;}//a와 b를 교환

여기에서는 정렬 상황을 보여주기 위해 원래 배열의 주소와 원소 개수를 기억하는 전역 변수를 선언할게요. 만약 정렬 상황을 보여주는 작업을 할 필요가 없다면 이 변수들도 필요없습니다.

int *origin;

int on;

이 책에서는 정수 형식 배열을 정렬하는 함수를 만들기로 할게요. 원소 형식에 관계없이 정렬하는 방법은 디딤돌 정렬 알고리즘 (C언어)를 참고하세요.

void ShellSort(int *base, int n);

int main(void)

{

    int arr[10] = { 9,4,3,10,5,8,7,6,2,1 };

여기에서는 정렬 상황을 보여주기 위해 원래 배열의 주소와 원소 개수를 전역 변수에 설정합니다.

    origin = arr;

    on = 10;

    ShellSort(arr, 10);

    return 0;

}

 

그리고 여기에서는 정렬 알고리즘을 수행하면서 배열의 원소 값을 교환할 때마다 콘솔 화면에 출력하도록 합시다. 실제 정렬 알고리즘에서는 정렬 과정에서 출력하는 부분을 정의할 필요는 없습니다. 따라서 여기에서 작성하는 ViewArr 함수를 주석 처리를 하면 정렬 알고리즘을 구현한 함수로 볼 수 있습니다.

void InsertionSort2(int *base, int size, int step);

void ViewArr(int *arr, int n);

void ShellSort(int *base, int size)

{

    int i, step;

쉘 정렬은 간격을 size/2을 초기값으로 설정하여 1/2씩 줄여나가면서 수행합니다.

    for (step = size / 2; step>0; step /= 2)//step의 폭을 1/2로 줄여간다.

    {

여기에서는 step에 따라 어떻게 배열 상태가 바뀌는지 출력하는 부분을 작성합시다. 만약 정렬 과정이 필요없다면 주석 처리하세요.

        printf("step:%d\n", step);

0, step, 2*step, ... 원소를 정렬한 후에 1, step+1, 2*step+1, ... 원소 정렬합니다. 이와 같은 작업을 step-1, 2*step – (step-1), 3*step – (step-1), ... 원소를 정렬하는 것까지 수행할 것입니다.

 

따라서 반복문을 0에서 step보다 작을 때까지 삽입 정렬2를 수행하게 구현합니다.

        for (i = 0; i<step; i++) //step 간격에 있는 요소들을 삽입정렬

        {

            InsertionSort2(base + i, size - i, step);

        }

    }

}

삽입 정렬2는 삽입 정렬과 비슷합니다. 삽입 정렬은 step이 1인 삽입 정렬2와 같습니다. 여기에서는 삽입 정렬2에 관한 설명은 생략할게요.

void InsertionSort2(int *base, int size, int step)

{

    int i, j;

    for (i = step; i<size; i += step)//정렬 대상 원소는 step 간격으로 이동

    {

 

        for (j = i; j>0; j -= step)//step 간격으로 앞으로 이동

        {

            if (base[j - step]>base[j])//앞쪽이 더 클 때

            {

                SWAP(base[j - step], base[j]);//교환

                ViewArr(origin, on);

            }

            else

            {

                break;

            }

        }

    }

}

테스트 목적으로 배열의 내용을 출력하는 함수입니다.

void ViewArr(int *arr, int n)

{

    int i = 0;

인덱스 0에서 마지막 요소까지 값을 출력합니다.

    for (i = 0; i<n; i++)

    {

        printf("%2d ", arr[i]);

    }

전체 요소 값을 출력한 후에 개행 문자를 출력합니다.

    printf("\n");

}

[그림 2.6] 쉘 정렬