귀하는 로그인되어 있지 않습니다. 이대로 편집하면 귀하의 IP 주소가 편집 기록에 남게 됩니다.스팸 방지 검사입니다. 이것을 입력하지 마세요!== 개요 == <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로 가져옴] == 각주 == <!--분류--> [[분류:알고리즘]] [[분류:정렬]] 편집 요약 가온 위키에서의 모든 기여는 크리에이티브 커먼즈 저작자표시-동일조건변경허락 라이선스로 배포된다는 점을 유의해 주세요(자세한 내용에 대해서는 가온 위키:저작권 문서를 읽어주세요). 만약 여기에 동의하지 않는다면 문서를 저장하지 말아 주세요. 또한, 직접 작성했거나 퍼블릭 도메인과 같은 자유 문서에서 가져왔다는 것을 보증해야 합니다. 저작권이 있는 내용을 허가 없이 저장하지 마세요! 취소 편집 도움말 (새 창에서 열림) 이 문서에서 사용한 틀: 틀:글씨 색 (편집)