정렬-버블 정렬(bubble sort)

*정렬-버블 정렬(Bubble Sort)

-오른쪽부터 왼쪽 방향으로 인접한 두 개의 숫자를 비교하여 교환작업 반복

-오른쪽에서 왼쪽으로 숫자가 옮겨가는 모습이 물속에서 거품이 올라오는 모양과 비슷하다고 하여 버블이라 불림

-버블소트는 1라운드에서 n-1회, 2라운드에서 n-2회가되며 비교 횟수는 n²/2 가 됨

-비교횟수는 입력 데이터의 순서와 상관없이 일정함

 

*버블 정렬의 예

-수열의 오른쪽 끝의 숫자와 그 옆의 숫자를 비교함(5 9 3 1 2 8 4 7 6)(비교)

-만약 오른쪽 끝의 숫자가 더 작다면 좌우의 숫자 교체(5 9 3 1 2 8 4 6 7)(이동)

-비교완료 후 한칸 왼쪽으로 옮겨 같은 방법으로 숫자 비교(5 9 3 1 2 8 4 6 7)(비교)

-(5 9 3 1 2 8 4 6 7)(이동)

-(5 9 3 1 2 4 8 6 7)(비교)

-(5 9 3 1 2 4 8 6 7)(이동) 

-(5 9 3 1 2 4 8 6 7)(비교)

-(5 9 3 1 2 4 8 6 7)(이동)

-(5 9 3 1 2 4 8 6 7)(비교)

-(5 9 3 1 2 4 8 6 7)(이동)

-(5 9 3 1 2 4 8 6 7)(비교)

-(5 9 1 3 2 4 8 6 7)(이동)

-(5 9 1 3 2 4 8 6 7)(비교)

-(5 1 9 3 2 4 8 6 7)(이동)

-(5 1 9 3 2 4 8 6 7)(비교)

-(1 5 9 3 2 4 8 6 7)(이동)

-1라운드 종료, 왼쪽 숫자 1은 정렬을 끝낸 것으로 간주하며 비교대상 제외

-오른쪽 끝에서 왼쪽으로 두 수를 비교하여 다시 작업 반복...

-정렬 완료(1 2 3 4 5 6 7 8 9)

 

 

 

 

---

이 포스팅에 작성한 내용은 이시다 모리테루, 미야자키 쇼이치, ⌜알고리즘 도감⌟, 김완섭 옮김, (주)제이펍, 2020 에서 발췌하였습니다.