Bubble Sort

Bubble Sort

• 배열의 연속된 두 원소의 크기를 비교하여 정렬하는 정렬 알고리즘
• 반복될 때 마다 가장 큰 원소부터 자신의 위치를 찾는다.
  • 번째 반복에서는 뒤에서 개의 (이미 정렬된) 원소를 제외해도 상관없다.

알고리즘

1. 주어진 배열의 제일 앞의 두 원소 , 를 선택한다.
2. 두 원소가 정렬된 상태라면 그대로 두고, 그렇지 않다면 두 원소의 위치를 서로 바꾼다.
3. (1), (2)를 배열의 처음부터 끝까지 반복한다.
4. (1), (2), (3)을 배열에 아무 변화가 없을 때 까지 반복한다.

시간 복잡도

	Compare	Change
Best
Average
Worst

공간 복잡도

	Support

예제

Phase 1 : [3, 4, 2, 5, 1]

• [3, 4, 2, 5, 1]
  • 3 < 4 이므로 변동 X
• [3, 4, 2, 5, 1]
  • 4 > 2 이므로 두 수를 바꿈
• [3, 2, 4, 5, 1]
  • 4 < 5 이므로 변동 X
• [3, 2, 4, 5, 1]
  • 5 > 1 이므로 두 수를 바꿈
• [3, 4, 2, 1, 5]

Phase 2 : [3, 2, 4, 1, 5]

• [3, 2, 4, 1, 5]
  • 2 < 3 이므로 변동 X
• [2, 3, 4, 1, 5]
  • 3 < 4 이므로 변동 X
• [2, 3, 4, 1, 5]
  • 4 > 1 이므로 두 수를 바꿈
• [2, 3, 1, 4, 5]
  • 4 < 5 이므로 변동 X
• [2, 3, 1, 4, 5]

Phase 3 : [2, 3, 1, 4, 5]

• [2, 3, 1, 4, 5]
  • 2 < 3 이므로 변동 X
• [2, 3, 1, 4, 5]
  • 3 > 1 이므로 두 수를 바꿈
• [2, 1, 3, 4, 5]
  • 3 < 4 이므로 변동 X
• [2, 1, 3, 4, 5]
  • 4 < 5 이므로 변동 X
• [2, 1, 3, 4, 5]

Phase 4 : [2, 1, 3, 4, 5]

• [2, 1, 3, 4, 5]
  • 2 > 1 이므로 두 수를 바꿈
• [1, 2, 3, 4, 5]
  • 2 < 3 이므로 변동 X
• [1, 2, 3, 4, 5]
  • 3 < 4 이므로 변동 X
• [1, 2, 3, 4, 5]
  • 4 < 5 이므로 변동 X
• [1, 2, 3, 4, 5]

Phase 5 : [1, 2, 3, 4, 5]

• [1, 2, 3, 4, 5]
  • 1 < 2 이므로 변동 X
• [1, 2, 3, 4, 5]
  • 2 < 3 이므로 변동 X
• [1, 2, 3, 4, 5]
  • 3 < 4 이므로 변동 X
• [1, 2, 3, 4, 5]
  • 4 < 5 이므로 변동 X
• [1, 2, 3, 4, 5]

Phase 6 : [1, 2, 3, 4, 5]

• Phase 5에서 변동이 없었으므로 정렬 완료

코드

def bubble_Sort(x):
	is_changed = False
	for i in range(len(x) - 1):
		is_changed = False
		for j in range(len(x) - 1):
			if x[j] > x[j+1]:
				is_changed = True
				temp = x[j+1]
				x[j+1] = x[j]
				x[j] = temp
		if is_changed == False:
			break
	return x

이 글은 Obsidian을 이용해 작성되었습니다.