🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘
정렬 - 버블 정렬
📍 버블 정렬(Bubble Sort)
👉🏻 가장 쉽게 생각할 수 있는 정렬 중 하나로 구현이 쉬우나 성능이 좋지는 않음
[4, 2, 3, 1]
// 앞에 있는 숫자와 그 뒤의 숫자를 비교해서 조건에 따라 자리를 바꿈
_ _
[2, 4, 3, 1]
_ _
[2, 3, 4, 1]
_ _
[2, 3, 1, 4]
// 4(마지막 원소) 자리가 고정되었음(정렬 완료)
_ _
[2, 3, 1] // 배열 유지
_ _
[2, 1, 3]
// 3(마지막 원소) 자리가 고정되었음
_ _
[1, 2]
// 남은 원소는 1 하나이므로 정렬 끝
📍 버블 정렬의 구현
[ bubble_sort.mjs ]
function BubbleSort(arr) {
// 배열이 n개라면 n-1만큼 정렬해야 함
for(let i = 0; i < arr.length - 1; i++) {
// 하나의 원소는 원소의 개수에서 -1만큼 정렬해야 함
for(let j = 0; j < (arr.length - i - 1); j++) {
if(arr[j] > arr[j+1]) {
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
let arr = [4, 2, 3, 1];
console.log("===== 정렬 전 =====");
console.log(arr);
BubbleSort(arr);
console.log("===== 정렬 후 =====");
console.log(arr);
📍 버블 정렬의 성능(빅 오 ver.)
👉🏻 길이 n 배열에서 반복문을 한 번 거칠 때마다 마지막 원소가 정렬됨
👉🏻 등차수열의 합의 모습이 됨 (n - 1) + (n - 2) + (n -3) + ... + 2 + 1
👉🏻 O(n^2)
📍 버블 정렬의 장단점
👉🏻 장점: 이해와 구현 간단함
👉🏻 단점: 성능이 좋지 않음