Bubble Sort (거품 정렬)
알고리즘 복습하기 정렬편 3탄
약 1분
알고리즘 포스팅 하며 복습하기 (정렬편) 📊
거품 정렬이란?
거품 정렬은 배열의 첫 번째 요소부터 시작하여 인접한 두 요소를 비교하여 순서를 바꾸는 방식으로 정렬하는 알고리즘입니다. 인접요소보다 현재요소가 크면 교환하고 작으면 그대로 두기에 큰 값부터 뒤에 정렬되는 방식입니다.
코드
const array = [1, 4, 2, 3, 5];
const bubbleSort = (arr) => {
for (let i = 0; i < arr.length; i++) {
for (let j = 1; j < arr.length - i; j++) {
if (arr[j] < arr[j - 1]) {
[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
}
}
}
return arr;
};
console.log(bubbleSort(array)); // [1, 2, 3, 4, 5]시간 복잡도
- 거품 정렬은 항상 2개의 요소를 비교하며 배열의 끝까지 탐색하기에 시간 복잡도는 **O(n^2)**입니다.
- Big O 표기법은 최악의 경우를 기준으로 표기