[알고리즘] #2. 버블정렬(거품정렬)

1. 버블정렬(bubble sort) 알고리즘

• 서로 인접한 두 원소를 비교하여 더 작은 값을 앞으로 보내어 정하는 알고리즘
• 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어있지 않으면 서로 교환
• 선택 정렬과 기본 개념이 유사
  → 버블정렬 : 요소를 교환 정렬 / 안정적 알고리즘 / 속도느림 / 간단하고 비효율적
  → 선택정렬 : 요소를 선택하여 정렬 / 불안정한 알고리즘 / 버블정렬에 비해 빠름 / 효율적
  ※ 알고리즘은 목록이나 배열에서 정렬 전 발생하는 동일한 순서로 동일한 키가 있는 요소가 안정적이라 간주

 

2. 버블정렬 알고리즘의 구현

첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를 비교 …

이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬.

 

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

int main() {
	int i, j, temp;
	int arr[10] = { 1, 9, 4, 6, 11, 10, 3, 15, 2, 13 };
	for (i = 0; i < 10; i++) {
		for (j = 0; j < 9 - i; j++) {
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
	for (i = 0; i < 10; i++)
		printf("%d ", arr[i]);

	return 0;
}

 

3. 버블정렬 알고리즘의 특징

3-1. 장점

• 구현이 간단하다.

3-2. 단점

• 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.
• 연산 수가 가장 많아 알고리즘 중에서 상대적으로 가장 느리고 효율성이 떨어지는 정렬방식.

→ 일반적으로 자료의 교환작업(SWAP)이 자료의 이동작업(MOVE)보다 더 복잡하기 때문에     
버블정렬은 단순성에도 불구하고 거의 쓰이지 않음

 

 

 

참고) https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

[알고리즘] 버블 정렬(bubble sort)이란 - Heee's Development Blog

 

참고) https://ko.gadget-info.com/difference-between-bubble-sort

버블 정렬과 선택 정렬의 차이점