알고리즘 (with JAVA)/기본 알고리즘
거품 정렬 (Bubble Sort)
백_곰
2023. 4. 27. 00:00
1. 개념 설명
(1) 거품 정렬은 서로 인접한 두 원소의 대소를 비교하고 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘이다.
2. 과정
- 실제로 수행되는 과정이며, 배열 0 인덱스부터 순차적으로 비교한다.
3. 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public class BubbleSort {
static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
int[] A = { 7, 2, 8, 10, 1 };
for(int i=0; i<A.length-1; i++) {
for(int j=0; j<A.length-1-i; j++) {
if(A[j]>A[j+1]) {
int tmp=A[j];
A[j]=A[j+1];
A[j+1]=tmp;
}
}
}
for(int i : A) {
System.out.print(i+" ");
}
}
}
|
cs |
4. 시간 복잡도
(1) 수행 횟수를 보면 (n-1) + (n-2) + ... + 2 + 1 --> n(n-1)/2가 나오게 된다.
(2) 그러므로, 버블 정렬에 시간 복잡도는 O(n²)이다.
( 시간 복잡도가 상당히 느리지만, 코드가 단순하므로 자주 사용된다고 한다. )
5. 공간 복잡도
(1) 주어진 배열 안에서 정렬이 일어나므로, 공간 복잡도는 O(n)이다.
6. 장점
(1) 코드가 매우 단순하며 직관적이다.
(2) 주어진 배열 안에서 정렬되기 때문에 다른 메모리 공간이 필요하지 않다.
( *제자리 정렬 (in-place sorting) )
(3) 안정 정렬이다.
7. 단점
(1) 시간 복잡도가 최선, 평균, 최악 모두 O(n²)이므로, 시간이 오래 걸리기 때문에 굉장히 비효율적이다.
(2) Swap이 많이 일어난다.