[알고리즘] 거품 정렬

버블 정렬이란?

버블 정렬은 두 개의 인접한 원소를 비교해 순서에 맞지 않으면 서로 교환하는 정렬 방식입니다. 이렇게 인접한 원소를 교환하는 모습이 마치 물 속의 거품과 비슷해 버블 정렬이라고 부르는 것입니다.

버블 정렬(bubble sort) 알고리즘의 예제

배열에 7, 4, 5, 1, 3이 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.

• 1회전

  • 첫 번째 자료 7을 두 번째 자료 4와 비교하여 교환하고, 두 번째의 7과 세 번째의 5를 비교하여 교환하고, 세 번째의 7과 네 번째의 1을 비교하여 교환하고, 네 번째의 7과 다섯 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 네 번 비교한다. 그리고 가장 큰 자료가 맨 끝으로 이동하므로 다음 회전에서는 맨 끝에 있는 자료는 비교할 필요가 없다.

• 2회전

  • 첫 번째의 4을 두 번째 5와 비교하여 교환하지 않고, 두 번째의 5와 세 번째의 1을 비교하여 교환하고, 세 번째의 5와 네 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 세 번 비교한다. 비교한 자료 중 가장 큰 자료가 끝에서 두 번째에 놓인다.

• 3회전

  • 첫 번째의 4를 두 번째 1과 비교하여 교환하고, 두 번째의 4와 세 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 두 번 비교한다. 비교한 자료 중 가장 큰 자료가 끝에서 세 번째에 놓인다.

• 4회전

  • 첫 번째의 1과 두 번째의 3을 비교하여 교환하지 않는다.

버블 정렬 구현

버블 정렬의 핵심은 비교 후 순서에 어긋나면 교환하는 것입니다.

각자 아래 목적에 맞게 분리되어야 하므로 반복문을 통해 숫자가 담겨있는 배열이나 리스트에 제대로 접근해야 합니다.

• 왼쪽 리스트: 인접한 원소의 순서가 맞지 않으면 바꿔줍니다.

• 오른쪽 리스트: 리스트 끝에서부터 정렬이 되어 있는 상태이므로 이 안에서 절대 자리를 바꾸면 안됩니다.

코드로 구현하면 아래와 같습니다.

void bubble_sort(int list[], int n) {
	int temp;
	for(int 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);
			}
		}
	}
}

버블 정렬의 시간 복잡도

버블 정렬 또한 반복문이 이중으로 들어가 있기 때문에
O($n^2$)입니다.

참고

https://github.com/gyoogle/tech-interview-for-developer
https://laurent.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EB%B2%84%EB%B8%94-%EC%A0%95%EB%A0%AC-bubble-sort