[C언어 알고리즘] 2.3.2 버블 정렬 알고리즘 구현

[C언어 알고리즘] 2.3.2 버블 정렬 알고리즘 구현

---

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

버블 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)

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

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

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

                교환(base[j-1],base[j])

 

//버블 정렬(Bubble Sort)

#include <stdio.h>

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

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

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

void BubbleSort(int *base, int n);

int main(void)

{

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

    BubbleSort(arr, 10);

    return 0;

}

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

void ViewArr(int *arr, int n);

void BubbleSort(int *base, int n)

{

    int i, j;

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

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

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

    {

내부 반복문은 앞에서부터 i개의 원소 중에 제일 큰 원소를 맨 뒤로 옮기는 작업을 수행합니다. 이를 위해 j를 1부터 i까지 순차적으로 이동하면서 j 앞의 원소가 더 크면 두 원소의 값을 교환하는 작업을 수행합니다. 이와 같은 작업을 반복 수행하면 제일 큰 원소가 맨 뒤로 이동합니다.

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

        {

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

            {

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

여기에서는 값을 변경할 때마다 결과를 화면에 출력하기 위해 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.3] 버블 정렬