[C] 버블 정렬 (bubble sort)

  가장 짧고 간단한 코드로 나타낼 수 있는 정렬 알고리즘이다. 하지만 이러한 알고리즘이 다 그렇듯 단점은 거의 모든 상황에서 최악의 성능을 보인다는 점이다. 시간 복잡도는 O(n^2)이다.

 적은 양의 데이터에서는 굳이 다른 정렬법을 쓰지 않아도 되는 성능을 발휘하지만, 현업에서는 방대한 양의 데이터를 관리하기 떄문에 버블정렬은 웬만해서는 안쓴다고 한다.

 버블 정렬은 1번째와 2번째, 2번째와 3번쨰 .... n-1번째와 n번째를 비교하여 정렬하고 그 다음엔 n-2, n-1번째 까지, 그 다음엔 n-3, n-2번째 까지 하나씩 줄여가면서 정렬한다. 

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

const int MAX_NUM = 100;

void swap(int *a, int *b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int main() {


	int arr[MAX_NUM];

	int count = 0;

	int i, j;

	srand(time(NULL));
	
	for (i = 0; i < MAX_NUM; i++) {
		arr[i] = rand() % 1000 + 1;
	}

	for (i = 0; i < MAX_NUM; i++) {
		for (j = 0; j < MAX_NUM - 1 - i; j++) {
			if (arr[j] > arr[j + 1]) {
				swap(arr + j, arr + j + 1);
				count++;
			}
		}
	}

	for (i = 0; i < MAX_NUM; i++) {
		printf("%d ", arr[i]);
		if ((i + 1) % 10 == 0) printf("\n");
	}

	printf("정렬한 횟수 : %d\n", count);

	return 0;

}