2025-07-30 22:10

Status:

Tags: 알고리즘

버블 정렬

가장 단순한 형태의 정렬 알고리즘 학습 용으로 배우긴 하지만 실제 사용은 안한다.

기본 아이디어

• 배열 처음부터 두개씩 비교
• 왼쪽이 더 크면 교환 아니면 넘어감
• 끝까지 가면 왼쪽이 제일 작고 오른쪽이 제일 큼

시간 복잡도

• 최악 평균 : O(n²)
• 최선 : O(n) 이미 정렬된 경우라 의미 없음

파이썬 코드

def bubble_sort(arr):
	n = len(arr)
	while True:
		swapped = False
		for i in range(1,n): # 처음부터 끝까지
			if arr[i-1] > arr[i] # 왼쪽이 오른쪽보다 크면
				arr[i-1], arr[i] = arr[i], arr[i-1] # 스왑
				swapped = True
		if not swapped:
			 break
		n -= 1
	return arr

보통은 삽입 정렬 이나 퀵 정렬 합병 정렬 쓰지 이거 안쓴다.

References

배열

버블 정렬 핸드북