[알고리즘] 버블 정렬 구현 (c언어)

🌿버블 정렬이란?

기본 정렬 알고리즘 중 하나이며, 인접한 두 원소의 크기를 비교하며 교환한다.

 

2중 for문으로 이루어지며 O(n^2)의 시간 복잡도를 가진다.

---

🌿작동 방식

편의상 오름차순 정렬을 기준으로 설명!

 

- 첫 루프에서

 

1번째와 2번째 비교 후 교환

2번째와 3번째 비교 후 교환

.

.

size-1번째와 size번재 비교후 교환

 

이러면 최댓값이 맨뒤에 하나 옮겨지게 된다.

 

- 두번째 루프에서 

1번째와 2번째 비교 후 교환

2번째와 3번째 비교 후 교환

.

.

size-2번째와 size-1번재 비교후 교환

 

역시 맨뒤 - 1 번째에 최댓값이 옮겨진다.

 

- 위 과정 반복!!

 

⭐그림을 통해 이해해 보자

첫번째 루프에서 최댓값이 오른쪽으로 옮겨지는 과정

 

여기서 중요한건 [i]와 [i+1]번째 비교시[ i+1]의 값이 더 작을때 교환을 해준다는 것이다.

 

만약 더 클 때 교환을 해준다면?!

 

최솟값이 맨 뒤로 가므로 내림차순 정렬이 완성된다.

---

🌿코드

#include <stdio.h>

void bubble_sort(int* arr, int size) {
	for (int i = size-1; i > 0; i--) {
		for (int j = 0; j < i; j++) {
			if (arr[j] > arr[j+1]) {
				int temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}
		}
	}
}

int main()
{
	int arr[5] = { 5, 3, 4, 2, 1 };

	printf("정렬 전\n");
	for (int i = 0; i < 5; i++) {
		printf("%d ", arr[i]);
	}

	bubble_sort(arr, 5);

	printf("\n정렬 후\n");
	for (int i = 0; i < 5; i++) {
		printf("%d ", arr[i]);
	}
}

---

🌿실행

---