5. 버블 정렬 (Bubble Sort)

정렬은 원소 값의 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업을 만한다.

정렬을 하면 검색을 보다 쉽게 할 수가 있는 것이 장점이다.

먼저 버블 정렬에 대해서 알아보자.

 

6

4

3

7

1

9

8

정렬 순서는 끝에서 부터 진행이 된다.

6

4

3

7

1

8

9

처음으로 8 과 9을 바꾸었다. 그 다음은 1과 8을 비교해서 앞에 위치한 값이 크면 바꿔주고 아니면 비교만 하고 교환은 하지 않는다.

6

4

3

1

7

8

9

---

1

6

4

3

7

8

9

여기까지의 과정을 봤을 때, 제일 작은 값 1을 맨 앞으로 가져온 것을 확인할 수가 있었다. 그러나 나머지 원소에 있어서도 똑같은 과정을 통해서 정렬을 해주어야한다. 원소 교환을 수행하는 패스의 횟수는 n-1 회이며, 이유는 n-1개의 요소 정렬이 끝나면 마지막 요소는 이미 맨 끝에 놓이기 때문이다.

 

이제 버블정렬을 코드로 구현해보자.

전체 변수에 있어서는 a[i] ~ a[n-1] 에대해 앞으로 스캔하면서 두 요소를 비교, 교환해야하고, 교환 시에는 a[j-1]  과 a[j] 를 교환하는 것이므로, 교환 역시 끝에서 부터 이루어지기 때문에 교환 인덱스 값 j는 1씩 감소하게 된다.

 

#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(void) {

	int i, nx;
	int* x; 

	puts("버블 정렬");
	printf("요소 개수 : ");
	scanf("%d", &nx);
	x = (int*)calloc(nx, sizeof(int));
	
	for (i = 0; i < nx; i++)
	{
		printf("x[%d] : ", i);
		scanf("%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;
}

여기서 구현한 버블함수를 개선하려면, 끝까지 패스가 되지 않아도 이미 정렬이 완료된 상태라면, 요소 교환하는 것을 멈추는 것을 표현해주어야 한다.

여기서 교환 횟수가 0이 되면 교환하는 반복문 작업을 멈추게끔 break를 걸면 비교 연산이 생략되게 되어 보다 짧은 시간이 걸릴 것이다.

void bubble(int a[], int n)
{
	int i,j;
    for(i=0;i<n-1;i++)
    {
    	int ex =0;// 교환 횟수 선언, 반복문에 선언되서 교환 작업이 끝나면 매번 초기화 된다.
    	for(j=n-1;j<i;j--)
        {	
        	if(a[j-1]>a[j])
        		swap(int, a[j-1],a[j]);
                ex ++;//교환 시 증가
        }
        if(ex==0)// 교환이 수행되지 않으면 종료
        {
        	break;
        }
    }
}

파이썬으로 구현하면 아래와 같이 쉽게 구현할 수 있다.

data = [6,4,3,7,1,9,8]

#전체 요소 길이, 즉 전체 요소를 살펴야하기 때문
for i in range(0, len(data)):
    # 비교횟수는 데이터 갯수 - 1 번만큼 비교
    for j in range(0, len(data)-1):
        # 앞의 데이터가 뒤의 데이터보다 크다면 swap
        if data[j]>data[j+1]:
            data[j], data[j+1] = data[j+1], data[j]

print(data)