알고리즘 개념 5. 버블 정렬 (Bubble sort)

 

- 인접한 두 항목을 비교하여, 기준을 만족하면 서로의 값을 교환하는 형식

- 선택정렬과 기본 개념이 유사하다

 

예를 들어, 오름차순 정렬을 하고싶을때!

 

기준: 인접한 두 항을 비교하여, 더 큰수가 뒤로 가도록 바꾼다

1회전 수행결과: 가장 큰 수가 맨 뒤로 간다

2회전 수행결과: 가장 큰 수 2개가 맨 뒤에 있다.

 

2회전 수행시에는, 1회전에서 완료한 맨 끝의 값을 제외하고 연산한다. 

 

 

비교연산횟수: n(n-1)/2

 

자리교환횟수: n(n-1)/2

 

시간복잡도: O(n^2)

 

장점?

- 단순한 개념, 구현하기 쉬움

단점?

- 비교횟수가 많아서 연산 속도가 느림, 대량데이터에 부적합

 

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