Chap 6-1. 버블 정렬(Bubble Sort)

6.1 버블 정렬

= 인접한 2개의 레코드를 비교하여 순서대로 되어 있지 않으면 서로 교환한다. 

즉, 두 개씩 비교해서 둘 중에 큰  숫자가 한 칸씩 뒤로 간다.

 

– 작은 수는 배열의 앞부분으로 이동하는데, 배열을 좌우가 아니라 상하로 그려보면 정렬하는 과정에서 작은 수가 마치 거품처럼 위로 올라가는 것을 연상케 한다.

 

[패스(pass)란? ]

 = 배열 전체를 근접한 2개씩 비교하여 큰 것이 뒤로 가게 하는 과정을 반복한다.

 

1 패스는  = 한 번 입력을 처음부터 끝까지 연속된 두 수를 비교하는 것을 말한다.

1 패스를 수행한 결과는  = 제일 큰 값이 제일 끝에 위치하게 된다. 1패스를 수행하여 제일 큰 값을 정렬하는 데 성공한 것이다. 

→ 그러므로 제일 큰 수를 제외하고 나머지들끼리 다시 위의 과정을 반복한다. (1, 2, 3...n패스를 반복하며 정렬을 수행한다.) 

전체 정렬이 완료되기 위해서 N개의 원소가 있다면 N-1번의 패스가 수행된다.

 

[의사코드]

입력: 크기가 n인 배열 A
출력: 정렬된 배열 A
1. for pass = 1 to n-1
2. for i = 1 to n-pass // n-1, n-2, n-3... 1까지 줄어들면서 반복 
3.   if (A[i-1] > A[i]) // 위의 원소가 아래의 원소보다 크면
4.      A[i-1] ↔ A[i] // 자리바꿈
5. return A

별도의 메모리 공간이 필요한 것이 아니라 제자리 정렬이다. 즉, 따로 결과 배열을 만들지 않고 입력 배열 안에서 정렬을 한다. 

 

[단점]

무조건 패스를 다 돈다. → 어떠한 경우에라도 무조건 2개씩 비교한다. 

즉, 중간에 정렬이 완료되어도 정렬 과정을 계속 진행한다. (n-1까지 비교)

 

 

[코드 구현]

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

#define N 8
#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))

void bubbleSort(int A[])
{
	int temp;

	printf("Before Sort : ");
	for (int j = 0; j < 0; j++) //배열 출력 
		printf("%d", A[j]);
	printf("\n");


	printf("\n <<<<<<<<<<<<<<<<< Bubble Sorting .... >>>>>>>>>>>>>>>>>>\n");
	for (int pass = 1; pass <= N - 1; pass++) //하나의 패스를 기준으로 
	{ // N-1번만 비교해도 된다. -> 마지막 패스에서 남은 것은 정렬할 필요가 없기 때문이다. 
		printf("  %d pass >> ", pass);
		for (int i = 1; i <= N - pass; i++) //순회하면서 비교한다. 
			if (A[i - 1] > A[i])
				SWAP(A[i - 1], A[i], temp);

		for (int j = 0; j < 0; j++) //배열 출력 
			printf("%d", A[j]);
		printf("\n");
	}

}

int main()
{
	int A[N] = {40, 10, 50, 90, 20, 80, 30, 60};
	bubbleSort(A);

	return 0;
}

 

[버블 정렬의 단점(무조건 pass를 다 수행한다) 극복을 위한 flag 사용 ]

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

#define N 8
#define FALSE 0
#define TRUE 1
#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))

void bubbleSort(int A[])
{
	int temp;

	printf("Before Sort : ");
	for (int j = 0; j < 0; j++) //배열 출력 
		printf("%d", A[j]);
	printf("\\n");

	printf("\\n <<<<<<<<<<<<<<<<< Bubble Sorting .... >>>>>>>>>>>>>>>>>>\\n");
	for (int pass = 1; pass <= N - 1; pass++) //정렬 과정 
	{
		int flag = FALSE;
		
		for (int i = 1; i <= N - pass; i++)
			if (A[i - 1] > A[i])
			{
				SWAP(A[i - 1], A[i], temp);
				flag = TRUE; // swap을 했다는 것은 아직 정렬이 안되었다는 의미이므로 정렬 TRUE 이다. 
			}
				
		if (flag == FALSE) //여기서 flag가 FALSE라는 것은 정렬을 수행하지 않았다는 것 = 정렬이 끝남 
			break;
		printf("  %d pass >> ", pass);

		for (int j = 0; j < N; j++) //배열 출력 
			printf("%d", A[j]);
		printf("\\n");
	}

	
	

}

int main()
{
	int A[N] = {40, 10, 50, 90, 20, 80, 30, 60};
	bubbleSort(A);

	return 0;
}

 

시간 복잡도

버블 정렬은 for-루프 속에서 for-루프 수행 – pass=1이면 (n-1)번 비교 – pass=2이면 (n-2)번 비교 ⋯ – pass=n-1이면 1번 비교

– 총 비교 횟수: (n-1) + (n-2) + ⋯ + 1 = n(n-1)/2

– 안쪽 for-루프의 if-조건이 True일 때의 자리바꿈은 O(1) 시간

즉, n(n-1)/2 x O(1) = O(n^2) x O(1)
= O(n^2)