반응형
버블 정렬(Bubble Sort)
-
기초적인 정렬 알고리즘(선택 정렬, 버블 정렬, 삽입 정렬)중 하나
- 수행 방법
- 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식
- 첫 번째 원소부터 마지막 원소까지 반복하여 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬
- 첫 번째 원소 부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리로 이동하는 모습이 물 속에서 물위로 올라오는 물방울 모양과 같다고 하여 버블(bubble) 정렬이라 지칭함.
- 버블 정렬 수행 과정
- 정렬되지 않은 {69, 10, 30, 2, 16, 8, 31, 22}의 자료들을 버블 정렬 방법으로 정렬하는 과정을 살펴보자.
- 인접한 두 원소를 비교하여 자리를 교환하는 작업을 첫 번째 원소부터 마지막 원소까지 차례로 반복하여 가장 큰 원소 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²)이 된다.
반응형
'연구개발 > Algorithm' 카테고리의 다른 글
정렬 알고리즘 - 퀵 정렬(Quick Sort) (0) | 2011.01.24 |
---|---|
정렬 알고리즘 - 병합 정렬(Merge Sort) (0) | 2011.01.24 |
정렬 알고리즘 - 삽입 정렬(Insert Sort) (0) | 2011.01.24 |
정렬 알고리즘 - 선택 정렬(Selection Sort) (0) | 2011.01.24 |
정렬 알고리즘 개념 (0) | 2011.01.24 |