이번 시간에는 버블 정렬에 대해서 알아보겠다.

버블정렬

오름차순으로 배열을 정렬하고자 한다면 왼쪽의 값이 오른쪽의 값보다 작아야 한다.

Fist pass를 보면, n개인 배열에서 n-1회 비교, 교환을 하고 나면 가장 작은 요소가 맨 처음으로 이동한다.

이어서 교환을 하면서 pass를 진행한다. 이 작업을 Third pass까지 진행 후에 요소의 정렬이 끝난다.

First pass는 n-1회 / Second pass는 n-2회 / Third pass는 n-3회 pass를 할때마다 정렬할 요소가 하나씩 줄어든다.

수행하는 패스의 횟수가 n회가 아니라 n-1회인 것은 n-1개 요소의 정렬이 끝나면 마지막 요소는 이미 끝에 놓이기 때문이다.

버블 정렬 프로그램을 구현

for(i = 0; i < n-1; i++)
{
	//a[i], a[i+1], ··· a[n-1]에 대해 
    //끝에서부터 앞쪽으로 스캔하면서 이웃하는 두 요소를 비교하고 교환한다.
}

*4이전은 정렬되어 있다고 가정

0   1  i-1  i  i+1     n-3 n-2 n-1   < index
0   1   4   6   4   5   8   7   9
                               j ->n-1
                          j가 1씩 감소     
            여기까지               
            
- 비교하는 두 요소의 인덱스를 j-1, j라 한다.
- 배열의 끝부터 스캔하기 떄문에 j의 시작점은 n-1이다.
- (a[j-1], a[j])의 값을 비교하여 앞쪽이 크면 교환한다.
- 그 이후의 비교, 교환 과정은 바로 앞쪽에서 수행해야 하므로 j의 값은 1씩 감소한다.
- i개의 요소는 정렬이 끝난 상태라고 가정힌다. 
- 정렬되어 있지 않는 부분은 a[i] ~ a[n-1]로 가정.
- 한 번의 패스에서는 j의 값이 i+1이 될 때까지 비교, 교환하면 된다.

버블 정렬 알고리즘은 (비교 교환하기 때문에) 안정적이다.

수식으로 표현하면,

n-1 + n-2 + ··· + 1 = n(n-1)/2 다.

교환 횟수의 평균값은 비교 횟수의 절반인 n(n-1)/4 회다.

예시1

#include <stdio.h>


int main()
{
	int i, j;
	int temp[8] = { 10, 2, 4, 5, 6, 7, 8, 9 };
	int swap;

	for (i = 0; i < 8; i++)
	{
		for (j = 0; j < 7 - i; j++)
		{
			if (temp[j] > temp[j + 1])
			{
				//swap 진행
				swap = temp[j];
				temp[j] = temp[j + 1];
				temp[j + 1] = swap;
			}
		}
	}

	for (i = 0; i < 8; i++)
		printf("%d", temp[i]);
}

<결과>

예시2

#include <stdio.h>
#include <stdlib.h>
#define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)

// 뒤에서 앞으로 검사 & 오름차순. 기존
void bubble(int a[], int n)
{
    int i, j;

    for (i = 0; i < n - 1; i++) {
        for (j = n - 1; j > i; j--) {
            if (a[j - 1] > a[j])
                swap(int, a[j - 1], a[j]);
        }
    }
}



int main() {
    int i, nx;
    int* x;

    puts("버블 정렬");
    printf("요소 개수 : ");
    scanf_s("%d", &nx);
    x = calloc(nx, sizeof(int));

    for (i = 0; i < nx; i++) {
        printf("x[%d] : ", i);
        scanf_s("%d", &x[i]);
    }

    bubble(x, nx);

    puts("오름차순으로 정렬했습니다.");

    for (i = 0; i < nx; i++) {
        printf("x[%d] = %d\n", i, x[i]);
    }

    free(x);

    return 0;
}

<결과>

핵심코드 및 비교

(1)
void bubble(int a[], int n)
{
   int i, j;

   for (i = n - 1; i > 0; i--) {
       for (j = 0; j < i; j++)
           if (a[j] > a[j + 1])
               swap(int, a[j], a[j + 1]);
   }
}

(1) == (2) 
// 뒤에서 앞으로 검사 & 오름차순. 기존
void bubble(int a[], int n)
{
    int i, j;

    for (i = 0; i < n - 1; i++) {
        for (j = n - 1; j > i; j--) {
            if (a[j - 1] > a[j])
                swap(int, a[j - 1], a[j]);
        }
    }
}

(3)//앞에서 뒤로 검사 & 오름차순. 
 void bubble2(int a[], int n)
 {
     int i, j;
 
     for (i = 0; i < n - 1; i++) {
         for (j = 0; j < n - 1 - i; j++) {
             if (a[j] > a[j + 1])
                 swap(int, a[j], a[j + 1]);
         }
     }
 }