버블 정렬 문서 원본 보기

{{위키데이터 속성 추적}}
{{알고리즘 정보
|이름       = 버블 정렬
|분류       = [[정렬 알고리즘]]
|그림       = Bubblesort-edited-color.svg
|그림설명   = 시각화된 버블 정렬 알고리즘.<ref>{{웹 인용|last=Cortesi |first=Aldo |title=Visualising Sorting Algorithms |url=https://corte.si/posts/code/visualisingsorting/index.html |date=27 April 2007 |accessdate=16 March 2017}}</ref>
|자료구조   = [[배열]]
|최악       = <math>O(n^2)</math> 비교, <math>O(n^2)</math> 교환
|최선       = <math>O(n)</math> 비교, <math>O(1)</math> 교환
|평균       = <math>O(n^2)</math> 비교, <math>O(n^2)</math> 교환
|공간복잡도 = <math>O(1)</math> 보조
}}
[[파일:Bubble sort animation.gif|섬네일]]

'''버블 정렬''' 또는 '''거품 정렬'''(-整列, {{llang|en|bubble sort|버블 소트}}, {{lang|en|sinking sort|싱킹 소트}})은 [[정렬 알고리즘]] 중 하나이다. [[시간 복잡도]]가 <math>O(n^2)</math>로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 이를 양방향으로 번갈아 수행하면 [[칵테일 정렬]]이 된다.

== 알고리즘 ==
버블 정렬은 기본적으로 배열의 두 수(<math>a</math>, <math>b</math>)를 선택한 뒤, 만약 그 두 수가 정렬되었다면 놔두고 아니라면 두 수를 바꾸는 방식으로 진행된다. 오름차순으로 정렬할 때는 <math>a<b</math>, 내림차순이라면 <math>a>b</math>여야 정렬된 것으로 판단한다. 이를 배열의 처음부터 끝까지 반복한다.

위 알고리즘을 배열에 아무 변화가 없을 때까지 반복한다.

== 예시 ==
다음과 같은 정렬되지 않은 배열이 있다고 가정한다. 프로그램은 이 배열을 오름차순으로 정렬해야 한다.

<math>[7, 2, 0, 1, 5, 6, 4]</math>

알고리즘은 배열의 첫 두 숫자(<math>7, 2</math>)를 비교한다. <math>7> 2</math>로 정렬되지 않았으니 두 수를 바꾼다.

<math>[2, 7, 0, 1, 5, 6, 4]</math>

이를 배열의 처음부터 끝까지 작업한다면 다음이 된다.

<math>[2, 0, 1, 5, 6, 4, 7]</math>{{인알|1회}}

가장 큰 수인 <math>7</math>이 정렬되었다. 이를 여러 번 반복한다면 다음과 같이 진행된다.

<math>[0, 1, 2, 5, 4, 6, 7]</math>{{인알|2회}}
<math>[0, 1, 2, 4, 5, 6, 7]</math>{{인알|3회}}
<math>[0, 1, 2, 4, 5, 6, 7]</math>{{인알|4회}}

{{인알|3회}}부터 {{인알|4회}}까지는 아무 변화가 없으니 모두 정렬된 것으로 정의한다.


== 소스 코드 ==
=== [[C (프로그래밍 언어)|C]] ===
<syntaxhighlight lang="c" line="1">
#include <stdio.h>
# define MAX 10

int* bubble_sort(int arr[], int n) {
    int i, j, temp;
    for (i=n-1; i>0; i--) {
        for (j=0; j<i; j++) {
            if (arr[j] > arr[j+1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    return arr;

}

int main() {
    int arr[MAX] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 };
    int* arr_new = bubble_sort(arr, MAX);
    for (int i = 0; i < MAX; i++) {
        printf("%d\n", *(arr_new+i));
    }
    return 0;
}
</syntaxhighlight>

=== [[C++]] ===
<syntaxhighlight lang="cpp" line="1">
#include <iostream>
using namespace std;
#include <iomanip>
using std::setw;

void printBubbles(const int bubbles[], const int n);
void lineup(int& large, int& small);
int main()
{
	const int n = 10;
	int bubbles[n] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 };

	cout << "Data items in original order\n";
	printBubbles(bubbles, n);
	for (int level = 0; level < n - 1; level++) {
		for (int i = 0; i < n - level - 1; i++) {
			if (bubbles[i] > bubbles[i + 1])
				lineup(bubbles[i], bubbles[i + 1]);
		}
	}
	cout << "\nData items in ascending order\n";
	printBubbles(bubbles, n);
	return 0;
}

void printBubbles(const int bubbles[], const int n) {
	for (int i = 0; i < n; i++)
		cout << setw(4) << bubbles[i];
	cout << endl;
}
void lineup(int& large, int& small) {
	int save = large;
	large = small;
	small = save;
}</syntaxhighlight>

=== [[C#]] ===
<syntaxhighlight lang="c#" line="1">
int[] data = new int[] { 3, 6, 2, 4, 1, 7, 9, 8, 5 };
int hold = 0;
int[] BubbleSort = new int[] { };

for(int i = 0; i < data.Length - 1; i++)
{
    for (int j = 0; j < data.Length - 1 - i; j++)
    {
        if (data[j] > data[j + 1])
        {
            hold = data[j];
            data[j] = data[j + 1];
            data[j + 1] = hold;
        }
    }
}

for (int i = 0; i < data.Length; i++)
{
    Console.WriteLine(data[i]);
} </syntaxhighlight>

=== [[F 샤프|F#]] ===
<syntaxhighlight lang="f#" line="1">
let sort (arr:'a[]) = 
  let arr = Array.copy arr
  let swap i j = 
    let tmp = arr.[i] in arr.[i] <- arr.[j]; arr.[j] <- tmp
  for i = arr.Length - 1 downto 0 do
    for j = 1 to i do
      if (arr.[j - 1] > arr.[j]) then swap (j-1) j
  arr

printfn "%A" (sort [|3;4;2;1|]) </syntaxhighlight>

=== JAVA ===
<syntaxhighlight lang="java" line="1">
void bubbleSort(int[] arr) {
    int temp = 0;
	for(int i = 0; i < arr.length - 1; i++) {
		for(int j= 1 ; j < arr.length-i; j++) {
			if(arr[j]<arr[j-1]) {
				temp = arr[j-1];
				arr[j-1] = arr[j];
				arr[j] = temp;
			}
		}
	}
	System.out.println(Arrays.toString(arr));
} </syntaxhighlight>

=== [[파이썬]] ===
<syntaxhighlight lang="python">
def bubbleSort(x):
	length = len(x)-1
	for i in range(length):
		for j in range(length-i):
			if x[j] > x[j+1]:
				x[j], x[j+1] = x[j+1], x[j]
	return x
</syntaxhighlight>

=== [[스칼라]] ===
<syntaxhighlight lang="scala">
def bubbleSort(arr: Array[Int]):Array[Int] =  {
  var tmp = 0
  for(i <- 0 until arr.length; j <- 1 until arr.length-i) {
    if (arr(j-1) > arr(j)) {
      tmp = arr(j-1)
      arr(j-1) = arr(j)
      arr(j) = tmp
    }
  }
  arr
}
</syntaxhighlight>

== 각주 ==
{{각주}}

== 외부 링크 ==
* [http://www.algorithm-code.com/wiki/Bubble_sort Bubblesort code]

{{정렬 알고리즘}}

[[분류:정렬 알고리즘]]
[[분류:안정 정렬]]
[[분류:비교 정렬]]