버블 정렬

버블 정렬은 정렬 알고리즘 중 가장 기본적인 형태로, 서로 인접한 두 요소를 비교하여 정렬하는 방식이다. 간단하지만, 효율성 측면에서는 다른 정렬 알고리즘에 비해 떨어진다.

작동 원리

1. 배열의 처음부터 시작하여 인접한 두 요소를 비교한다.
2. 두 요소의 순서가 잘못된 경우, 서로 교환한다.
3. 배열의 끝까지 한 번 순회하면 가장 큰 값이 맨 끝으로 이동한다.
4. 정렬되지 않은 부분만 다시 순회하며 이 과정을 반복한다.
5. 5 모든 요소가 정렬될 때까지 위의 과정을 계속한다.

시간 복잡도와 공간 복잡도

시간 복잡도

• 최선의 경우: 데이터가 이미 정렬된 경우 교환 없이 확인만 진행하면 되므로 O(n)이다.
• 최악의 경우: 데이터가 역순으로 정렬된 경우로 $O(n^2)$이다.
• 평균: $O(n^2)$

공간 복잡도

• O(1): 제자리 정렬이므로, 추가 메모리 사용 없음

장점과 단점

장점

• 구현이 매우 간단함
• 배열의 크기가 작거나 데이터가 거의 정렬된 경우 사용할 수 있음

단점

• 비효율적이며, 데이터가 큰 경우 잘 사용하지 않음
• 일반적으로 자료의 교환 작업이 자료의 이동 작업보다 더 복잡함

전체 코드

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_SIZE 10
#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )

int list[MAX_SIZE];
int n;

void bubble_sort(int list[], int n) {
	int i, j, temp;
	for (i = n - 1; i > 0; i--) {
		for (j = 0; j < i; j++)
			if (list[j] > list[j + 1])
				SWAP(list[j], list[j + 1], temp);
	}
}

int main(void) {
	int i;
	n = MAX_SIZE;
	srand(time(NULL));
	for (i = 0; i < n; i++) 
		list[i] = rand() % 100;

	bubble_sort(list, n);
	for (i = 0; i < n; i++)
		printf("%d ", list[i]);
	printf("\n");
	return 0;
}

출처
C언어로 쉽게 풀어쓴 자료구조 - 천인구