정렬 알고리즘 - 버블 정렬(Bubble Sort)

버블 정렬(Bubble Sort)

 

• 기초적인 정렬 알고리즘(선택 정렬, 버블 정렬, 삽입 정렬)중 하나
  
  
• 수행 방법
• 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식
• 첫 번째 원소부터 마지막 원소까지 반복하여 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬
• 첫 번째 원소 부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리로 이동하는 모습이 물 속에서 물위로 올라오는 물방울 모양과 같다고 하여 버블(bubble) 정렬이라 지칭함.

• 버블 정렬 수행 과정
• 정렬되지 않은 {69, 10, 30, 2, 16, 8, 31, 22}의 자료들을 버블 정렬 방법으로 정렬하는 과정을 살펴보자.

1. 인접한 두 원소를 비교하여 자리를 교환하는 작업을 첫 번째 원소부터 마지막 원소까지 차례로 반복하여 가장 큰 원소 69를 마지막 자리로 정렬한다.

 

2. 버블 정렬을 수행하여 나머지 원소 중에서 가장 큰 원소 31을 끝에서 두번째 자리로 정렬한다.

 

 

3. 버블 정렬을 수행하여 나머지 원소 중에서 가장 큰 원소 30을 끝에서 세번째 자리로 정렬한다.

 

 

4. 버블 정렬을 수행하여 나머지 원소 중에서 가장 큰 원소 22를 끝에서 네번째 자리로 정렬한다.

 

 

5. 버블 정렬을 수행하여 나머지 원소 중에서 가장 큰 원소 16을 끝에서 다섯번째 자리로 정렬한다.

 

 

6. 버블 정렬을 수행하여 나머지 원소 중에서 가장 큰 원소 10을 끝에서 여섯번째 자리로 정렬한다.

 

 

7. 버블 정렬을 수행하여 나머지 원소 중에서 가장 큰 원소 8을 끝에서 일곱 번째 자리로 정렬한다.

 

 

• 버블 정렬 알고리즘

 

• 버블 정렬 알고리즘의 분석
• 메모리 사용 공간
• n개의 원소에 대하여 n개의 메모리 사용
  
  
• 연산 시간
• 최선의 경우 : 자료가 이미 정렬되어있는 경우

- 비교 횟수 : i 번째 원소를 (n-1)번 비교하므로, n(n-1)/2 번

- 자리교환횟수 : 자리교환이 발생하지 않는다.

• 최악의 경우 : 자료가 역순으로 정렬되어있는 경우

- 비교 횟수 : i 번째 원소를 (n-1)번 비교하므로, n(n-1)/2 번

- 자리교환횟수 : i 번째 원소를 (n-1)번 교환하므로 n(n-1)/2 번 

 

• 평균 시간 복잡도는 O(n²)이 된다.