거품 정렬

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

거품 정렬(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++[편집]

 1 #include <iostream>
 2 using namespace std;
 3 #include <iomanip>
 4 using std::setw;
 5 
 6 void printBubbles(const int bubbles[], const int n);
 7 void lineup(int& large, int& small);
 8 int main()
 9 {
10 	const int n = 10;
11 	int bubbles[n] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 };
12 
13 	cout << "Data items in original order\n";
14 	printBubbles(bubbles, n);
15 	for (int level = 0; level < n - 1; level++) {
16 		for (int i = 0; i < n - level - 1; i++) {
17 			if (bubbles[i] > bubbles[i + 1])
18 				lineup(bubbles[i], bubbles[i + 1]);
19 		}
20 	}
21 	cout << "\nData items in ascending order\n";
22 	printBubbles(bubbles, n);
23 	return 0;
24 }
25 
26 void printBubbles(const int bubbles[], const int n) {
27 	for (int i = 0; i < n; i++)
28 		cout << setw(4) << bubbles[i];
29 	cout << endl;
30 }
31 void lineup(int& large, int& small) {
32 	int save = large;
33 	large = small;
34 	small = save;
35 }

Java[편집]

 1 void bubbleSort(int[] arr) {
 2     int temp = 0;
 3 	for(int i = 0; i < arr.length; i++) {
 4 		for(int j= 1 ; j < arr.length-i; j++) {
 5 			if(arr[j]<arr[j-1]) {
 6 				temp = arr[j-1];
 7 				arr[j-1] = arr[j];
 8 				arr[j] = temp;
 9 			}
10 		}
11 	}
12 	System.out.println(Arrays.toString(arr));
13 }

파이썬[편집]

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

바깥 고리[편집]