거품 정렬

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
무작위 배열수의 거품 정렬 예
거품_정렬 편집 된 색상

거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.

예제[편집]

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

55 07 78 12 42
07 55 78 12 42  첫 번째 패스
07 55 78 12 42
07 55 12 78 42
07 55 12 42 78  두 번째 패스
07 55 12 42 78
07 12 55 42 78
07 12 42 55 78  세 번째 패스
07 12 42 55 78  네 번째 패스
07 12 42 55 78  다섯번째 패스
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[편집]

int temp[9] = { 3, 2, 1, 5, 4, 7, 8, 0, 6 };
int tempCount = 9;
int hold=0, loop, i;

for (loop = 0; loop < tempCount - 1; loop++) {
    for (i = 0; i < tempCount - 1 - loop; i++) {
        if (temp[i] > temp[i+1]) {
            hold = temp[i];
            temp[i] = temp[i+1];
            temp[i+1] = hold;
        }
    }
}

for (i = 0; i < tempCount; i++) {
    printf("%d", temp[i]);
}

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

Java[편집]

public void bubbleSort(int a[]) {
        int size = a.length;
        for(int i=size-1; i>0; i--) {
            System.out.printf("\n버블 정렬 %d 단계 : ", size-i);
            for(int j=0; j<i; j++) {
                if(a[j] > a[j+1]) {
                    swap(a,j,j+1);
                }
                System.out.printf("\n\t");
                for(int v : a) {
                    System.out.printf("%3d ", v);
                }
            }            
        }
        System.out.println();
    }
   public  void swap(int a[], int idx1, int idx2) {
        int temp = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = temp;
    }

파이썬[편집]

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

바깥 고리[편집]