const bubbleSort = (arr) => {
const length = arr.length;
for (let i = 0; i < length; i++) {
for (let j = i + 1; j < length; j++) {
if (arr[i] > arr[j]) {
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
}
return arr;
};
console.log(bubbleSort([3, 6, 1, 8, 20]));
만약 전체 배열내 인지 개수가 n 개라면 루프 돌면서 n, n - 1, n - 2 ... 1 진행됨
따라서 n(n-1)/2, 즉 만큼의 시간 복잡도를 가진다
temp로 저장하는 식으로 구현한 부분을 동적할당으로 리팩토링했다. (뿌듯)
참고 사이트 https://nyajjyang-portfolio.tistory.com/17
swap이 진행되지 않은 경우, if break 문으로 바로 루프를 끝내고 다음 루프를 돌도록 구현하면 된다.
const OptimizationBubbleSort = (arr) => {
const start = Date.now();
const length = arr.length;
for (let i = 0; i < length; i++) {
let swapped = false;
for (let j = i + 1; j < length; j++) {
if (arr[i] > arr[j]) {
[arr[i], arr[j]] = [arr[j], arr[i]];
swapped = true;
}
if (!swapped) break;
}
}
const end = Date.now();
console.log(`Execution time at optimized Bubble Sort ${end - start} ms`);
return arr;
};
const bubbleSort = (arr) => {
const start = Date.now();
const length = arr.length;
for (let i = 0; i < length; i++) {
for (let j = i + 1; j < length; j++) {
if (arr[i] > arr[j]) {
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
}
const end = Date.now();
console.log(`Execution time at Bubble Sort ${end - start}ms`);
return arr;
};
let a = [];
for (let i = 1; i < 100000; i++) {
a.push(i);
}
console.log(OptimizationBubbleSort(a));
console.log(bubbleSort(a));
비교해보면 최적화한 버블정렬은 2ms
밖에 안나는데,
최적화하지 않은 정렬은 루프를 끝내지않고 하나하나 비교하면서 다 돌기 때문에 10156ms
이나 걸린다. (시간 차이가 엄청나다!)
if (!swapped) break;의 스코프를 첫 번째 for문으로 옮기면 더욱 효율적으로 최적화할 수 있을 것 같아요.
만약 정렬되어 있는 배열이라면, i = 0인 루프 한 번만 돌았을 때 모든 정렬이 끝나면서 O(n)의 시간복잡도를 가질 수 있으니까요!