Gaon12: 시작

2023-03-28T06:09:30Z

시작

새 문서

== 개요 ==
<code>Bubble Sort</code>는 인접한 두 수를 비교하여 큰 수를 뒤로 보내는 간단한 정렬 알고리즘으로 <math>O(n^2)</math>의 시간 복잡도를 갖는다. 다른 정렬 알고리즘에 비해 속도가 상당히 느린 편<ref>일반적으로 가장 빠른 정렬 알고리즘은 <code>Quick Sort</code>로 시간 복잡도 <math>O(nlogn)</math> 이다.</ref>이지만, 코드가 단순하기 때문에 자주 사용된다.

원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 <code>Bubble Sort</code>라는 이름을 가지게 되었다.

== 정렬 과정 ==
다음과 같이 다섯 개의 숫자가 주어졌을 때, <code>Bubble Sort</code>로 정렬하는 방법은 다음과 같다.

{| class="wikitable" style="text-align: center;"
! 인덱스 !! 0 !! 1 !! 2 !! 3 !! 4
|-
| 값 || 5 || 3 || 7 || 9 || 1
|}

=== 첫번째 순회 ===

1. 먼저 '''5와 3 을 비교했을때 3보다 5가 더 큰 수 이므로, 두 수의 자리를 교체'''한다.

* '''교체 전'''
{| class="wikitable" style="text-align: center;"
! 인덱스 !! 0 !! 1 !! 2 !! 3 !! 4
|-
| 값 || <code>5</code> || <code>3</code> || 7 || 9 || 1
|}

* '''교체 후'''
{| class="wikitable" style="text-align: center;"
! 인덱스 !! 0 !! 1 !! 2 !! 3 !! 4
|-
| 값 || <code>3</code> || <code>5</code> || 7 || 9 || 1
|}

<hr>

2. 다음, '''오른쪽으로 한 칸 이동하여 5와 7을 비교'''한다. 여기서는 이미 큰 수 (7) 가 뒤에 있으므로 교체하지 않는다.
{| class="wikitable" style="text-align: center;"
! 인덱스 !! 0 !! 1 !! 2 !! 3 !! 4
|-
| 값 || 3 || <code>5</code> || <code>7</code> || 9 || 1
|}

<hr>

3. 다시 '''오른쪽으로 한 칸 이동하여 7와 9을 비교'''한다. 여기서도 이미 큰 수 (9) 가 뒤에 있으므로 교체하지 않는다.
{| class="wikitable" style="text-align: center;"
! 인덱스 !! 0 !! 1 !! 2 !! 3 !! 4
|-
| 값 || 3 || 5 || <code>7</code> || <code>9</code> || 1
|}

<hr>

4. 다시 '''오른쪽으로 한 칸 이동하여 9와 1을 비교''한다. 9가 1보다 더 큰 수 이므로, 두 수의 자리를 교체한다.
{| class="wikitable" style="text-align: center;"
! 인덱스 !! 0 !! 1 !! 2 !! 3 !! 4
|-
| 값 || 3 || 5 || 7 || <code>1</code> || <code>9</code>
|}

==== 첫번째 순회 정리 ====
한 번의 순회가 끝났다. 모든 원소를 한 번 씩 들러본 결과, 다섯 개의 숫자 중 가장 큰 수인 9가 파도처럼 밀려 맨 마지막, 즉 정렬이 완료 되었을 때의 자신의 자리를 찾아갔다.

여기서 다음번 순회 부터는 모든 원소를 방문할 필요가 없다.<ref>가장 큰 수 9는 정렬 된 후 자신이 있어야 할 위치에 도착했기 때문</ref>

위와 같은 과정이 한 차례 진행될 때마다, 뒤에서부터 정렬이 완료된 원소들이 하나 씩 위치하게 되는 것을 볼 수 있다. 정렬이 완료된 원소들은 다시 정렬 될 필요가 없다.

따라서 두 번째 순회 부터는 이미 정렬이 완료된 원소들을 제외한 원소들만 방문하여 정렬해 주면 된다.

=== 두번째 순회 ===
나머지 원소들의 자리도 찾아주기 위해 '''{{글씨 색|white|black|9}}'''를 제외한 원소들을 처음부터 다시 반복하여 비교해 보자.

{| class="wikitable" style="text-align: center;"
! 인덱스 !! 0 !! 1 !! 2 !! 3 !! 4
|-
| 값 || 3 || 5 || 7 || 1 || '''{{글씨 색|white|black|9}}'''
|}

<hr>

1. '''3과 5 를 비교'''했을 때 이미 큰 수( 5 ) 가 뒤에 있으므로 자리를 교체하지 않는다.

{| class="wikitable" style="text-align: center;"
! 인덱스 !! 0 !! 1 !! 2 !! 3 !! 4
|-
| 값 || <code>3</code> || <code>5</code> || 7 || 1 || '''{{글씨 색|white|black|9}}'''
|}

</hr>

2. 다음 '''오른쪽으로 한 칸 이동하여 5와 7을 비교'''한다. 이미 큰 수( 7 ) 가 뒤에 있으므로 교체하지 않는다.

{| class="wikitable" style="text-align: center;"
! 인덱스 !! 0 !! 1 !! 2 !! 3 !! 4
|-
| 값 || 3 || <code>5</code> || <code>7</code> || 1 || '''{{글씨 색|white|black|9}}'''
|}

</hr>

3. 다시 '''오른쪽으로 한 칸 이동하여 7와 1을 비교'''합니다. '''7이 1보다 더 큰 수 이므로, 두 수의 자리를 교체'''한다.

* '''교체 전'''
{| class="wikitable" style="text-align: center;"
! 인덱스 !! 0 !! 1 !! 2 !! 3 !! 4
|-
| 값 || 3 || 5 || <code>7</code> || <code>1</code> || '''{{글씨 색|white|black|9}}'''
|}

* '''교체 후'''
{| class="wikitable" style="text-align: center;"
! 인덱스 !! 0 !! 1 !! 2 !! 3 !! 4
|-
| 값 || 3 || 5 || <code>1</code> || <code>7</code> || '''{{글씨 색|white|black|9}}'''
|}

==== 두번째 순회 정리 ====
두 번째 순회가 완료 되었다. 남은 네 개의 원소 중 가장 큰 수인 '''{{글씨 색|white|black|7}}'''이 자신의 자리를 찾아갔다.

=== 세번째 순회 ===
나머지 세 개의 원소들을 다시 처음부터 순회해 준다.

{| class="wikitable" style="text-align: center;"
! 인덱스 !! 0 !! 1 !! 2 !! 3 !! 4
|-
| 값 || 3 || 5 || 1 || '''{{글씨 색|white|black|7}}''' || '''{{글씨 색|white|black|9}}'''
|}

<hr>

1. '''3과 5 를 비교'''했을때 이미 큰 수( 5 ) 가 뒤에 있으므로 자리를 교체하지 않는다.

{| class="wikitable" style="text-align: center;"
! 인덱스 !! 0 !! 1 !! 2 !! 3 !! 4
|-
| 값 || <code>3</code> || <code>5</code> || 1 || '''{{글씨 색|white|black|7}}''' || '''{{글씨 색|white|black|9}}'''
|}

<hr>

2. 다음 '''오른쪽으로 한칸 이동하여 5와 1을 비교'''한다. '''5가 1보다 더 큰 수 이므로, 두 수의 자리를 교체'''해 준다.

* '''교체 전'''
{| class="wikitable" style="text-align: center;"
! 인덱스 !! 0 !! 1 !! 2 !! 3 !! 4
|-
| 값 || 3 || <code>5</code> || <code>1</code> || '''{{글씨 색|white|black|7}}''' || '''{{글씨 색|white|black|9}}'''
|}

* '''교체 후'''
{| class="wikitable" style="text-align: center;"
! 인덱스 !! 0 !! 1 !! 2 !! 3 !! 4
|-
| 값 || 3 || <code>1</code> || <code>5</code> || '''{{글씨 색|white|black|7}}''' || '''{{글씨 색|white|black|9}}'''
|}

==== 세번째 순회 정리 ====
세번째 순회가 완료 되었다. 남은 세 개의 원소 중 가장 큰 수인 '''{{글씨 색|white|black|5}}'''가 자신의 자리를 찾아갔다.

=== 네번째 순회 ===
나머지 두 개의 원소들을 다시 처음부터 순회해 준다.

{| class="wikitable" style="text-align: center;"
! 인덱스 !! 0 !! 1 !! 2 !! 3 !! 4
|-
| 값 || 3 || 1 || '''{{글씨 색|white|black|5}}''' || '''{{글씨 색|white|black|7}}''' || '''{{글씨 색|white|black|9}}'''
|}

<hr>

1. '''3과 1을 비교'''한다. '''3이 1보다 더 큰 수 이므로, 두 수의 자리를 교체'''해 준다.
* '''교체 전'''
{| class="wikitable" style="text-align: center;"
! 인덱스 !! 0 !! 1 !! 2 !! 3 !! 4
|-
| 값 || <code>3</code> || <code>1</code> || '''{{글씨 색|white|black|5}}''' || '''{{글씨 색|white|black|7}}''' || '''{{글씨 색|white|black|9}}'''
|}

* '''교체 후'''
{| class="wikitable" style="text-align: center;"
! 인덱스 !! 0 !! 1 !! 2 !! 3 !! 4
|-
| 값 || <code>1</code> || <code>3</code> || '''{{글씨 색|white|black|5}}''' || '''{{글씨 색|white|black|7}}''' || '''{{글씨 색|white|black|9}}'''
|}

==== 네번째 순회 정리 ====
네번째 순회로 정렬이 완료되었다. 원소들이 큰 순서대로 뒤로 밀려가 거품처럼 정렬되는 모습을 볼 수 있다.

== 알고리즘 분석 ==
=== 비교 횟수 ===
버블 정렬은 한번의 순회를 마칠 때 마다 '''비교 대상이 하나씩 줄어들기 때문'''에, 전체 원소의 개수가 <math>n</math>개 라고 할 때, 총 <math>n-1</math>번 순회하면 정렬이 끝난다.

위의 예제에서는 총 원소 개수가 5개 이므로, <math>4 + 3 + 2 + 1 = 10</math>번 비교하게 된다. 이를 수식으로 일반화 시키면 다음과 같다.

<math>(n-1)+(n-2)+...+2+1=(n-1) \times n \div 2 = \frac{n(n-1)}{2}</math>

=== 자리 교환 횟수 ===
최선의 경우<ref>이미 정렬된 원소들이 주어진 경우</ref>, 자리 교환이 한번도 이루어 지지 않으므로, 시간복잡도에 영향을 미치지 않게 된다.

하지만 최악의 경우<ref>역순으로 정렬된 원소들이 주어진 경우</ref>, 원소를 비교 할 때마다 자리 교환이 일어나므로, 자리 교환 횟수 또한 비교 횟수와 같이 <math>\frac{n(n-1)}{2}</math> 가 된다.

따라서 평균적으로 <math>O(n^2)</math> 의 시간복잡도를 가지게 된다.

== 코드 ==
'''순회할 원소의 개수가 하나씩 줄어든다는 점'''을 적용한 코드 예제이다.

<syntaxhighlight lang="C">
int main()
{
int N = 5; //배열의 길이
int i, j, temp;
int data[] = { 5, 3, 7, 9, 1 };

// Bubble Sort
for (i = 0; i < N; i++) {
for (j = 0; j < N-(i+1); j++) {
if (data[j] > data[j+1]) {
// 자리교환
temp = data[j+1];
data[j+1] = data[j];
data[j] = temp;
}
}
}
}
</syntaxhighlight>

== 정리 ==
<code>Bubble Sort</code>는 이처럼 이해하기도 쉽고 코드도 단순하지만, 이라는 시간복잡도 때문에 비교할 데이터의 개수가 많을 수록 성능이 저하된다.

예제에서는 원소의 개수가 5개 뿐이라 10번의 연산만 하면 되었지만, 데이터의 개수가 만 개만 되어도 무려 '''약 오천만 번'''의 비교 연산을 필요로 하기 때문에 <code>Bubble Sort</code>는 데이터의 개수가 적은 경우에 주로 사용하게 됩니다.

[https://bowbowbow.tistory.com/10 CC BY로 가져옴]

== 각주 ==


[[분류:알고리즘]] [[분류:정렬]]

거품 정렬 - 편집 역사

Gaon12: 시작