거품 정렬

버블 정렬

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

무작위 배열수의 거품 정렬 예

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

예제

오름차순으로 정렬하는 버블 정렬의 과정은 다음과 같다.

55 07 78 12 42  초기값[파란색은 sorting]
07 55 78 12 42  첫 번째 패스(pass)
07 55 78 12 42
07 55 12 78 42
07 55 12 42 78  두 번째 패스(pass)
07 55 12 42 78
07 12 55 42 78
07 12 42 55 78  세 번째 패스(pass)
07 12 42 55 78  네 번째 패스(pass)
07 12 42 55 78  다섯 번째 패스(pass)
07 12 42 55 78  정렬 끝

의사코드로 나타낸 알고리즘

procedure bubbleSort( A : list of sortable items ) defined as:
  for each i in 1 to length(A) do:
       for each j in length(A) downto i + 1 do:
         if A[ j ] < A[ j - 1 ] then
           swap( A[ j ],  A[ j - 1 ] )
         end if
       end for
  end for
end procedure

소스 코드

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.Count() - 1; i++)
{
    for (int j = 0; j < data.Count() - 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.Count(); 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
}

외부 링크

• Bubblesort code