시간복잡도
시간복잡도를 계산하면, (n-1) + (n-2) + (n-3) + .... + 2 + 1 => n(n-1)/2이므로, O(n^2) 이다. 또한, Bubble Sort는 정렬이 돼있던 안돼있던, 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간복잡도가 O(n^2) 으로 동일하다.
공간복잡도
주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 이다.
그림 설명
- 첫번째 for문을 통해 모든 배열 마지막 숫자 전까지를 탐색한다.
- 두번째 for문을 통해 i값이 증가함에 따라 i값보다 한자리 앞의 숫자까지 탐색한다.
- 만약 해당 숫자가 다음 숫자보다 클 경우 위치를 변경시켜 준다.
- 첫번째 i = 0 일 경우를 모두 수행하고 나면 배열 중 가장 큰 수가 맨 뒤로 정렬 된다.
- 두번째 i = 1일 경우를 모두 수행하면 나면 배열 중 두번째 큰 수가 맨 뒤 앞에 정렬된다.
- 이를 반복한다.
function solution(arr) {
let answer = arr;
for ( let i = 0; i < arr.length - 1; i++ ) {
for ( let j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j+1]) {
[arr[j], arr[j+1]] = [arr[j+1], arr[j]];
}
}
}
return answer;
}
let arr = [13, 5, 11, 7, 23, 15];
console.log(solution(arr));장점
-
구현이 매우 간단하고, 소스코드가 직관적이다.
-
정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않다. => 제자리 정렬(in-place sorting)
-
안정 정렬(Stable Sort) 이다.
단점
-
시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장히 비효율적이다.
-
정렬 돼있지 않은 원소가 정렬 됐을때의 자리로 가기 위해서, 교환 연산(swap)이 많이 일어나게 된다.
Conclusion
정렬 알고리즘 중에 가장 직관적인 Bubble Sort에 대해 알아봤다. 기술 면접에서도 종종 나오는 정렬 알고리즘으로 알아두면 좋다.
버블 정렬 응용 (Special Sort) - 구글 인터뷰
- 양의 정수, 음의 정수의 순서에 변화를 주지 말고 음의 정수를 앞으로 정렬해라
- 첫번째 for 문에 의해 arr 배열의 앞 숫자 갯수 만큼 반복한다.
- 두번째 for 문에 의해 다음 인덱스가 음수일 경우 자리를 바꾼다.
(처음 실행될 경우 arr 배열 마지막 인덱스까지 음수가 있으면 앞의 양수와 자리를 바꾼다.) - 배열 마지막에 음수가 있을 경우 j for문이 실행될 때마다 한칸씩 앞으로 떙겨져 음수가 양수 앞에 정렬된다.
function solution(arr) {
let answer = arr;
for ( let i = 0; i < arr.length - 1; i++ ) {
for ( let j = 0; j < arr.length - i - 1; j++) {
if ( arr[j] > 0 && arr[j+1] < 0) {
[arr[j], arr[j+1]] = [arr[j+1], arr[j]];
}
}
}
return answer;
}
let arr=[1, 2, 3, -3, -2, 5, 6, -6];
console.log(solution(arr));
