[C언어 알고리즘] 2.4.2 선택 정렬 알고리즘 구현

[C언어 알고리즘] 2.4.2 선택 정렬 알고리즘 구현

---

이번에는 선택 정렬 알고리즘을 구현해 보아요.

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

    반복(i:=n;  i>1  ; i:= i-1)

        반복(max=0,j:=1; j<i ; j:=j+1)

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

                max := j

        temp: = base[i-1]

        base[i-1] = base[max]

        base[max] = temp

 

//선택 정렬(Selection Sort)

#include <stdio.h>

 

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

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

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

void SelectionSort(int *base, int n);

int main(void)

{

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

    SelectionSort(arr, 10);

    return 0;

}

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

void ViewArr(int *arr, int n);

void SelectionSort(int *base, int n)

{

    int i, j;

    int maxi;

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

선택 정렬은 이중 반복문을 사용합니다. 외부 반복문은 정렬할 범위를 축소해 나가면서 진행합니다.

    for (i = n; i>1; i--)//정렬할 범위를 축소해 나갑니다.

    {

선택 정렬의 내부 반복문은 인덱스 0에서 마지막 원소 중에 제일 큰 값을 찾아 맨 마지막 원소와 교환하는 작업을 수행합니다.

        maxi = 0;

        for (j = 1; j<i; j++)

        {

            if (base[maxi]<base[j])//더 큰 원소를 만나면

            {

                maxi = j;

            }

        }

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

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

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

    }

}

 

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

void ViewArr(int *arr, int n)

{

    int i = 0;

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

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

    {

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

    }

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

    printf("\n");

}

[그림 2.4] 선택 정렬