- [JavaScript] 버블정렬2025년 01월 11일
- KIMJAVAN
- 작성자
- 2025.01.11.:28
728x90버블 정렬 (Bubble Sort)
버블 정렬은 가장 간단한 정렬 알고리즘 중 하나로, 두 인접한 요소를 비교하여 크기 순서에 맞게 반복적으로 교환하는 방식으로 동작합니다. 정렬이 끝날 때까지 가장 큰 값(또는 작은 값)이 거품처럼 끝으로 이동하기 때문에 버블 정렬이라 부릅니다.
동작 원리
- 배열의 처음부터 시작해서 두 개의 인접한 요소를 비교합니다.
- 두 요소가 잘못된 순서(예: 오름차순에서 앞 값이 더 크거나, 내림차순에서 더 작음)라면 교환합니다.
- 배열의 끝까지 이 과정을 반복하면 가장 큰 값이 배열의 마지막으로 이동합니다.
- 이 과정을 배열의 길이만큼 반복하면서 정렬을 완성합니다.
장단점
- 장점: 구현이 매우 쉽다.
- 단점: 시간 복잡도가 비효율적이다 (O(n2)O(n^2)).
- 적합한 경우: 데이터가 거의 정렬되어 있는 경우.
예시 코드 (JavaScript로 구현)
1. 오름차순 버블 정렬
const bubbleSort = (array) => { const arr = array.slice(); // 원본 배열을 복사 const n = arr.length; for (let i = 0; i < n - 1; i++) { // 총 n-1번 반복 for (let j = 0; j < n - 1 - i; j++) { // 점점 범위를 줄여감 if (arr[j] > arr[j + 1]) { // 잘못된 순서라면 // 두 값을 교환 [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; } } } return arr; }; const an = [5, 1, 4, 2, 8]; console.log(bubbleSort(an)); // [1, 2, 4, 5, 8]
2. 내림차순 버블 정렬
const bubbleSortDesc = (array) => { const arr = array.slice(); const n = arr.length; for (let i = 0; i < n - 1; i++) { for (let j = 0; j < n - 1 - i; j++) { if (arr[j] < arr[j + 1]) { // 내림차순이므로 반대로 비교 [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; } } } return arr; }; const an = [5, 1, 4, 2, 8]; console.log(bubbleSortDesc(an)); // [8, 5, 4, 2, 1]
버블 정렬 동작 예시
배열: [5, 1, 4, 2, 8] (오름차순 정렬)
1단계 (첫 번째 패스):
- 비교: 5와 1 → 교환 → [1, 5, 4, 2, 8]
- 비교: 5와 4 → 교환 → [1, 4, 5, 2, 8]
- 비교: 5와 2 → 교환 → [1, 4, 2, 5, 8]
- 비교: 5와 8 → 그대로 → [1, 4, 2, 5, 8]
2단계 (두 번째 패스):
- 비교: 1과 4 → 그대로 → [1, 4, 2, 5, 8]
- 비교: 4와 2 → 교환 → [1, 2, 4, 5, 8]
- 비교: 4와 5 → 그대로 → [1, 2, 4, 5, 8]
3단계 (세 번째 패스):
- 비교: 1과 2 → 그대로 → [1, 2, 4, 5, 8]
- 비교: 2와 4 → 그대로 → [1, 2, 4, 5, 8]
결과: [1, 2, 4, 5, 8]
시간 복잡도
- 최선의 경우 (이미 정렬된 경우): O(n)O(n) → (최적화를 추가하면)
- 평균/최악의 경우: O(n2)O(n^2)
'자바스크립트 > JavaScript' 카테고리의 다른 글
[JavaScript] 삽입정렬 (0) 2025.01.11 [JavaScript] 선택정렬 (0) 2025.01.11 [JavaScript] bigO (0) 2025.01.11 [JavaScript] 알고리즘 공부기록 : 팩토리얼 / 법칙 (1) 2025.01.11 [JS] 알고리즘 - 초급 (0) 2024.12.19 다음글이전글이전 글이 없습니다.댓글
스킨 업데이트 안내
현재 이용하고 계신 스킨의 버전보다 더 높은 최신 버전이 감지 되었습니다. 최신버전 스킨 파일을 다운로드 받을 수 있는 페이지로 이동하시겠습니까?
("아니오" 를 선택할 시 30일 동안 최신 버전이 감지되어도 모달 창이 표시되지 않습니다.)