정렬 알고리즘 - 버블 정렬(Bubble sort)

버블 정렬

• 버블 정렬은 두 인접한 원소를 검사하여 정렬하는 방법이다.
• 시간 복잡도가 $O(n^{2})$로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다.
• 양방향으로 번갈아 수행하면 칵테일 정렬이 된다.
• 정렬 알고리즘 중 가장 단순한 알고리즘이다.

 

정렬 알고리즘 시간 복잡도 비교

버블 정렬 장단점

장점

• 코드가 단순하여 구현하기 쉽다. (이해하기 쉬움)
• 적은 양의 데이터에서는 시간이 오래 걸리지 않아 적절하다.

단점

• 시간이 오래 걸린다.
• 비효율적인 방법이다. (성능이 좋지 않음)
• 실업무에서 사용하기 어렵다. (데이터가 많을 경우 시간이 오래 걸림)

 

Python Code

def bubbleSort(x):
	length = len(x)-1
	for i in range(length):
		for j in range(length-i):
			if x[j] > x[j+1]:
				x[j], x[j+1] = x[j+1], x[j]
	return x

 

Java Code

void bubbleSort(int[] arr) {
    int temp = 0;
	for(int i = 0; i < arr.length - 1; i++) {
		for(int j= 1 ; j < arr.length-i; j++) {
			if(arr[j]<arr[j-1]) {
				temp = arr[j-1];
				arr[j-1] = arr[j];
				arr[j] = temp;
			}
		}
	}
	System.out.println(Arrays.toString(arr));
}