버블 정렬

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

버블 정렬

시각화된 버블 정렬 알고리즘.[1]
분류	정렬 알고리즘
자료 구조	배열
최악 시간복잡도	${\displaystyle O(n^{2})}$ 비교, ${\displaystyle O(n^{2})}$ 교환
최선 시간복잡도	${\displaystyle O(n)}$ 비교, ${\displaystyle O(1)}$ 교환
평균 시간복잡도	${\displaystyle O(n^{2})}$ 비교, ${\displaystyle O(n^{2})}$ 교환
공간복잡도	${\displaystyle O(1)}$ 보조

알고리즘

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

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

예시

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

${\displaystyle [7,2,0,1,5,6,4]}$

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

${\displaystyle [2,7,0,1,5,6,4]}$

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

${\displaystyle [2,0,1,5,6,4,7]}$1회

가장 큰 수인 ${\displaystyle 7}$이 정렬되었다. 이를 여러 번 반복한다면 다음과 같이 진행된다.

${\displaystyle [0,1,2,5,4,6,7]}$2회 ${\displaystyle [0,1,2,4,5,6,7]}$3회 ${\displaystyle [0,1,2,4,5,6,7]}$4회

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

소스 코드

C

#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;
}

C++

#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;
}

C#

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]);
}

F#

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|])

JAVA

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));
}

파이썬

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

스칼라

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
}