거품 정렬
위키백과 ― 우리 모두의 백과사전.
거품 정렬(영어: Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복합도가 O(n2)로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다.
목차 |
[편집] 예제
오름차순으로 버블정렬되어질 자료가 다음과같이 주어져있다고 한다.
55 07 78 12 42
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
[편집] 복잡도(complexity)
윗 알고리즘은 중첩된 두개의 for-loop에서 n(n-1)/2(→ n-1,n-2...0)의 비교연산이다. 즉, 된다. 만약에 테이블안 총자료수 N의 k요소들만 정렬되어져야 한다면 시간복잡도는 거의 O(kN)될 것이다.
[편집] 자바 소스코드
public void bubbleSort() { int i,j; TableEntry temp; for(i=1;i<N;i++) //N 테이블크기(자료의 총수) for(j=N;j>i;j--) if(table[j].key<table[j-1].key) { temp=table[j]; table[j]=table[j-1]; table[j-1]=temp; } }