728x90
반응형
설명
서로 인접한 두 원소의 대소를 비교하고, 조건(오름차순, 내림차순 등)에 맞지 않다면 자리를 교환하면서 정렬하는 알고리즘이다. Selection Sort와 유사하다.
과정
배열의 크기 : N (0~N-1)
- 1회전은 i=0 부터 i와 i+1번째 원소, 즉 자신과 자신의 오른쪽 수를 비교해서 조건에 맞지 않는다면 서로 교환한다.
- 1회전이 끝나면 가장 큰 원소가 맨 뒤로 이동해있으므로 다음 회전에서 마지막 원소는 제외된다.
- 2회전도 i=0부터 1번과 동일하게 수행한다. 그러면 두번째로 큰 수가 마지막에서 두번째에 위치한다.
- 3회전에서는 동일하게 수행해준다. 0~N-3까지만 확인하게 된다.
⇒ 1회전에서는 0개 제외
⇒ 2회전에서는 1개 제외
⇒ 3회전에서는 2개 제외
⇒ N회전에서는 N-1개 제외
구현(Java)
private static void bubbleSort(int[] arr) { //오름차순
int n = arr.length;
for (int k = 0; k < n; k++) { //제외할 원소 수
// n-1은 마지막원소는 제외하기 위해서 -k는 제외해야하는 원소 수만큼 추가로 빼주기
for (int i = 0; i < n-1-k; i++) {
if(arr[i] > arr[i+1]) { //조건에 어긋나는 경우 교환
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
}
}
- k는 제외할 원소의 개수이다.
- i는 비교할 배열의 인덱스이다. i와 i+1번째 원소를 비교해준다.
- 오름차순 정렬인 함수이므로 arr[i] > arr[i+1] 인 경우, 두 원소를 swap한다.
- 마지막 원소는 비교할 원소가 없기 때문에 n-1으로 범위를 지정해준다.
- 추가로 뒤에서 k개의 원소를 제외해야하기 때문에 n-1-k의 범위가 된다.
시간복잡도와 공간 복잡도
시간복잡도
(n-1) + (n-2) + (n-3) + ... + 2 + 1 = n(n+1)/2로 O(n^2)의 시간 복잡도를 갖는다. 정렬이 이미 되어있던 안되어있던 항상 for문은 실행되기 때문에 최선, 평균, 최악의 경우 모두 시간 복잡도가 O(n^2)이다.
공간복잡도
주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(n)
장점
- 구현이 간단하고, 소스코드가 직관적이다.
- 다른 메모리 공간을 필요로 하지 않는다.
- 안정 정렬(Stable Sort)
단점
- 시간 복잡도가 모두 O(n^2)으로 비효율적
- 교환(swap) 연산이 많이 발생하며, 교환 연산은 메모리 공간을 차지한다.
QA
더보기
교환 연산이 많이 발생하는게 왜 단점인가?
=> 메모리 공간을 필요로 하기 때문에
더보기
개선할 수 있는 BubbleSort?관련 문제 : https://www.acmicpc.net/problem/1838
=> 중간에 flag 변수를 선언하여 회전을 돌 때 교환할 원소가 없는 경우 바로 종료
참조
728x90
반응형
'이론 공부 > 알고리즘' 카테고리의 다른 글
[알고리즘] 선택 정렬 Selection Sort (0) | 2022.04.19 |
---|