버블 정렬

여러분들이 프로그래밍을 하시면서 한 번쯤은 들어봤을 법한 정렬방식 입니다. 바로 버블 정렬 이라는 방식인데요, 많이 들어본 이름인 만큼 구현하기도 쉽고, 이해하기도 쉽습니다만 구현과 이해가 쉬운만큼 성능에서는 조금 아쉬운 모습을 보여주지요.

아래의 이미지는 3, 2, 4, 1이 순서대로 저장된 배열을 오름차순으로 정렬하는 과정을 보여주고 있습니다. 이 이미지를 통해

버블 정렬의 과정을 소개하도록 할게요.

중간에 생략이 있긴한데, 대충 어떻게 비교되고 교환되는지 예상하실 수 있을거라 생각하고 뛰어 넘겼습니다.

위의 이미지를 보시면 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는데, 이게 버블정렬의 정렬 방식입니다. 

두 데이터를 비교하여, 정렬 순서상 위치가 바뀌어야 하는 경우에 두 데이터의 위치를 바꿔나가는 거죠. 

물론 한 번에 정렬이 되지 않는 경우도 있기 때문에 마지막 인덱스까지 비교했다 하더라도 맨 처음 인덱스로 돌아가 

정렬이 완전히 될 때까지 반복문을 돌 필요가 있습니다.

여기서 왜 버블 정렬이라는 이름이 붙었는지 의아해 하실 수 있는데, 앞에서부터 순서대로 비교하고 교환하는 과정이 거품이 일어나는 모습에 비유되어 버블 정렬이라는 이름이 붙었답니다.(딱히 중요하진 않은 내용입니다.ㅎ)

자, 그럼 코드를 봅시다.

#include

void BubbleSort(int arr[], int Len) {
	for (int i = 0; i < (Len - 1); i++) {
		for (int j = 0; j < (Len - i - 1); j++) {
			if (arr[j] > arr[j + 1]) {
				int Temp = arr[j + 1];
				arr[j + 1] = arr[j];
				arr[j] = Temp;
			}
		}
	}
}

int main() {
    int arr[4]={3,2,4,1};
    BubbleSort(arr,sizeof(arr)/sizeof(int));

    for(int i=0;i<4;i++){
        printf("%d ", arr[i]);
    }
    puts("");
    return 0;
}

의외로 간단하죠?

BubbleSort 함수를 보시면 이중 포문이 있는데, 이 이중 포문이 버블 정렬의 핵심이라 보시면 됩니다.

여기선 단지 코드 암기가 아니라 바깥쪽 for문의 반복 조건과 안쪽 for문의 반복조건에 대한 정확한 이해가

필요합니다.