[자료구조][C++]버블 정렬

버블 정렬

버블 정렬은 가장 큰 수를 맨 마지막으로 이동시키면서 정렬하는 방법입니다. 

즉 메모리에

3

9

5

1

6

2

8

4

7

이렇게 저장되어 있다면 

0번 index와 바로 그다음 index인 1번 index를 비교하여 앞의 index의 값이 더 크면 두 수를 swap 하고 아니면 그대로 둡니다.

그리고 비교 index의 값을 1씩 증가시켜 1번 index와 2번 index를 비교합니다. 

이런 비교를 "배열의 길이 - 1" 만큼 반복하면 맨 마지막 index에 가장 큰 수가 위치하게 됩니다.

3

5

1

6

2

8

4

7

9

이렇게 가장 큰 수인 9가 맨 마지막 index에 위치하게 됩니다. 

 

(배열의 길이가 n이라고 가정)

이러한 비교를 또 "배열의 길이 - 1" 만큼 반복하면 되는데 한 번 수행할 때마다 n-1, n-2... 위치의 index들은 값이 고정되므로 값의 비교 횟수를 1씩 감소시키면서 진행합니다.

 

코드

int arData[9] = { 3,9,5,1,6,2,8,4,7 };
	int nSize = 0;
	int nCount = 0;
	int nSortCount = 0;
	int nDstIdx = 0;
	int nSrcIdx = 0;
	
	nSize = 9;
	nCount = nSize - 1;
	nSortCount = nCount;
	for (int i = 0; i < nCount; i++) {
		nDstIdx = 0;
		nSrcIdx = nDstIdx + 1;
		for (int j = 0; j < nCount; j++) {
			if (arData[nDstIdx] > arData[nSrcIdx]) {
				swapData(arData[nDstIdx], arData[nSrcIdx]);
			}

			nDstIdx++;
			nSrcIdx = nDstIdx + 1;
		}
		nSortCount--;
		printData(arData, nSize);
	}

swapData() 함수는 두 수의 값을 변경하는 함수입니다.

printData() 함수는 배열의 모든 값을 출력해 주는 함수입니다.

 

버블 함수 이름의 이유

가장 큰 수가 계속해서 뒤로 이동하는 모습이 마치 파도의 거품이 이동하는 것 같다 하여 붙여진 이름으로 미국식 유머(?)를 통해 나온 이름이라고 합니다.