[C언어 알고리즘] 2.5.2 삽입 정렬 알고리즘 구현

[C언어 알고리즘] 2.5.2 삽입 정렬 알고리즘 구현

---

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

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

    반복(i:=1;  i<n  ; i:= i+1)

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

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

                temp: = base [j-1]

                base[j-1] = base [j]

                base[j] = temp

            아니면

                루프 탈출

 

//삽입 정렬(Insertion Sort)

#include <stdio.h>

 

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

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

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

void InsertionSort(int *base, int n);

int main(void)

{

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

    InsertionSort(arr, 10);

    return 0;

}

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

void ViewArr(int *arr, int n);

void InsertionSort(int *base, int n)

{

    int i, j;

 

    ViewArr(base, n);//현재 상태 출력

삽입 정렬은 이중 반복문을 사용합니다. 외부 반복문은 정렬할 범위를 확대해 나가면서 진행합니다.

    for (i = 1; i<n; i++)//정렬할 범위를 확대해 나갑니다.

    {

삽입 정렬의 내부 반복문은 인덱스 i에서 앞쪽으로 이동하면서 앞쪽 원소가 더 크면 자리를 교환하는 작업을 수행합니다. 이를 수행하면 인덱스 0에서 i까지 원소는 정렬 상태를 유지합니다.

        for (j = i; j>0; j--)

        {

            if (base[j - 1]>base[j])//앞쪽 원소가 더 크면

            {

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

여기에서는 값을 변경할 때마다 결과를 화면에 출력하기 위해 ViewArr 함수를 호출하고 있습니다. 실제 정렬 알고리즘에서 이 함수는 필요가 없습니다. 따라서 실제 정렬 알고리즘을 구현할 때 ViewArr 함수 호출 부분은 주석 처리하세요.

                ViewArr(base, n);//상태 출력

            }

삽입 정렬에서는 인덱스 i의 원소 외에는 정렬 상태에서 인덱스 i 요소를 포함하여 정렬하기 위해 자리를 찾는 것입니다. 만약 앞쪽 원소가 더 크지 않다면 더 이상 앞쪽들 원소하고 비교할 필요가 없으므로 반복문을 탈출합니다.

            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.5] 삽입 정렬