반응형
Bubble Sort 특징
- 매 Round마다 최소 1개의 카드가 올바른 포지션에 자리잡게 됨
- 가장 큰숫자가 뒤로가게 됨
- 최대 카드 숫자 (N)만큼의 Round를 돌아야함
- O(N^2)
Round 0 (Init)
7 6 4 5 3 2
Round 1
6 4 5 3 2 7
Round 2
4 5 3 2 6 7
Round 3
4 3 2 5 6 7
Round 4
3 2 4 5 6 7
Round 5
2 3 4 5 6 7
Round 6 (Final Check)
2 3 4 5 6 7
Bubble Sort 최적화
- 매 라운드마다 제일 큰 숫자가 맨 뒤로 감
- 매 라운드마다그 전 라운드의 마지막 숫자를 볼 필요가 없음
Round 0 (Init)
7 6 2 4 3 5
Round 1
6 2 4 3 5 7
[Resources]
[1] Let's Learn Algorithms: An Introduction to Bubble Sort - (https://youtu.be/iDU_D2Oxock)
반응형
