1. 거품 정렬(Bubble Sort)?
거품 정렬은 인접한 원소들끼리 비교하여 큰 것을 뒤로 보내서 점차적으로 정렬하는 알고리즘입니다.
2. 예시
5
|
8
|
7
|
1
|
3
|
데이터를 가지고 직접 거품 정렬을 해봅시다.
1. 가장 큰 수를 뒤로 보내기 위해 인접한 수끼리 비교를 행하여 교환해준다.
5
|
8
|
7
|
1
|
3
|
5
|
8
|
7
|
1
|
3
|
5
|
7
|
8
|
1
|
3
|
5
|
7
|
8
|
1
|
3
|
5
|
7
|
1
|
8
|
3
|
5
|
7
|
1
|
8
|
3
|
5
|
7
|
1
|
3
|
8
|
5
|
7
|
1
|
3
|
8
|
5
|
7
|
1
|
3
|
8
|
5
|
1
|
7
|
3
|
8
|
5
|
1
|
7
|
3
|
8
|
5
|
1
|
3
|
7
|
8
|
5
|
1
|
3
|
7
|
8
|
1
|
5
|
3
|
7
|
8
|
1
|
5
|
3
|
7
|
8
|
1
|
3
|
5
|
7
|
8
|
1
|
3
|
5
|
7
|
8
|
4. 특징
거품 정렬은 인접한 원소끼리 교환하는 특성 때문에 정렬과정에서 원소들의 순서가 보존된다. (Stable)
거품 정렬은 별도의 데이터를 저장하기 위한 배열이 필요하지 않다. (Inplace)
5. C를 이용한 구현
6. 사다리 타기
거품 정렬은 인접한 원소끼리 교환하는 특성 때문에, 사다리 타기의 결과가 주어질경우 원소의 교환이 발생하는 것을 기억해놓을 경우 그 결과가 나오는 사다리를 만들어 낼 수 있습니다.
댓글 없음:
댓글 쓰기