버블 정렬 알고리즘

버블 정렬 알고리즘

 

버블 정렬은 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복하는 정렬 알고리즘이다.

자료들이 정렬되는 모습이 마치 보글보글 거품처럼 올라오는 모습이라 버블 정렬이라고 한다는데 잘 모르겠다..

 

이런식으로 붙어있는 요소들간의 비교를 해서 변경을 해야한다면 스왑을하고 그게 아니라면 비교만 하고 넘어간다.

코드로 한번 구현을 해보았다.

 

void bubble(int a[], int element)
{
	for (int i = 0; i < element - 1; i++)
		for (int j = 0; j < element - 1 - i; j++)
			if (a[j] > a[j + 1])
			{
				int temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
			}
}

1. 매개변수로 비교할 배열과, 그 배열안의 요소가 몇개인지 받는다.

 

2. 첫번째 for문에서 요소의 수 -1 만큼 for문을 돈다.  -1을 하는 이유는

(ex. {요소1,요소2,요소3,요소4}   ->  요소1,요소2  /  요소2,요소3  /  요소3,요소4 )

이런식으로 4개의 요소가 있으면 3번만 비교를 하면 전부 비교가 끝나기 때문이다.

 

3. 두번째 for문은 요소의 수 -1 에서 i를 뺀만큼 for문을 도는데..

그 이유는  배열의 첫번째,끝 어디서 비교를 시작하더라도 비교와 교환을 통해 1자리는 확정이 나기 때문이다.

 

(ex. {6,3,2,1}   -> 6,3 비교 6 이더 큼 (스왑) / 6,2 비교 6 이더 큼 (스왑), 마지막 6,1비교 6 이더 큼 (스왑)) 

이런식으로 6이라는 최대값의 자리는 확정이 났기때문에 굳이 비교를 또 할 필요가 없는것이다.

 

i가 돌때마다 한자리씩 자리가 확정이 나는것이기 때문에 i를 빼주어야한다.

 

실행 해보기

#include <stdio.h>
#include <stdlib.h>


void bubble(int a[], int element)
{
	for (int i = 0; i < element - 1; i++)
		for (int j = 0; j < element - i - 1; j++)
			if (a[j] > a[j + 1])
			{
				int temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
			}
}

int main(void)
{
	int count=0;
	int* a;

	printf("몇개의 요소를 정렬하실건가요?: ");
	scanf_s("%d", &count);
	a = calloc(count, sizeof(int));

	puts("요소의 값들을 입력받습니다.\n");

	for(int i=0;i<count;i++)
	{
		printf("a[%d]의 값을 입력해주세요: ",i);
		scanf_s("%d", &a[i]);
	}

	puts("\n요소의 값들을 정렬합니다.\n");
	bubble(a, count);

	for (int j = 0; j < count; j++)
	{
		printf("a[%d]의 값은 : %d\n", j,a[j]);
	}
	
    free(a);

	return 0;
}

 

 

이런식으로 위의 예시로 든 요소들의 정렬이 잘 된것을 볼 수 있다.