버블 정렬(Bubble Sort)

• 버블 정렬(Bubble sort)

서로 인접한 두 원소를 비교하여 정렬되어 있지 않은 경우에 교환하는 정렬 알고리즘

*일련의 비교 과정을 패스(pass)라고 함

비교 횟수: (n-1) + (n-2) + ... + 1 = n(n-1)/2 이므로 시간복잡도 O(n^2) (best, avg, worst 모두)

 

#include <stdio.h>
#include <stdlib.h>
#define swap(x, y) do {int t = x; x = y; y = t;} while(0)

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

int main(void) {
	int i, nx;
	int* x; //배열 첫 요소 포인터

	puts("버블 정렬");
	printf("요소 개수: ");
	scanf_s("%d", &nx);
	x = calloc(nx, sizeof(int));

	for (i = 0; i < nx; i++) {
		printf("x[%d]: ", i);
		scanf_s("%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이면 정렬을 마칠 수 있음

 

void bubble(int a[], int n) {
	int i, j;
	for (i = n-1; i > 0; i--) {
		int exchg = 0; // 교환 횟수
		for (j = 0; j < i; j++) {
			if (a[j] > a[j + 1]) {
				swap(a[j], a[j + 1]);
				exchg++;
			} 
		}
		if (exchg == 0) break;
	}
}