버블 정렬
버블 정렬(bubble sort)
수열을 정렬하는 알고리즘 중 하나. 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘.
시간 복잡도: O(n2)
다음과 같이 정렬되지 않은 배열이 있다고 가정한다. 프로그램은 이 배열을 오름차순으로 정렬해야한다.
[ 7, 2, 0, 1, 5, 6, 4 ]
알고리즘은 배열의 첫 두글자(7, 2)를 비교한다. 7 > 2 로 정렬되지 않았으니 두 수를 바꾼다.
[ 2, 7, 0, 1, 5, 6, 4 ]
7은 다시 0과 자리를 바꾸고 이를 배열 끝까지 작업하면 다음과 같이 된다.
[ 2, 0, 1, 5, 6, 4, 7 ] - 한번 회전
가장 큰 수인 7이 정렬되었다. 이를 여러번 반복한다면 다음과 같이 진행된다.
[ 0, 1, 2, 5, 4, 6, 7 ] - 두번 회전
[ 0, 1, 2, 4, 5, 6, 7 ] - 세번 회전
[ 0, 1, 2, 4, 5, 6, 7 ] - 네번 회전
세번째와 네번째의 차이가 없으므로 모두 정렬된 것으로 정의한다.
장단점
- 장점
- 구현이 매우 간단하다.
- 단점
- 순서에 맞지 않은 요소를 인접한 요소와 교환한다.
- 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.
일반적으로 자료의 교환작업이 자료의 이동작업보다 더 복잡하기 때문에 버블정렬은 단순성에도 불구하고 거의 쓰이지 않는다.
버블 정렬(bubble sort) js 코드
// 기본 버블 정렬 함수
const bubbleSort = (arr) => {
for (let i = 0; i < arr.length; i++) {
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;
}
}
}
return arr;
};
// 최적화된 버블 정렬 함수
const optimizedBubbleSort = (arr) => {
let i, j;
let len = arr.length;
let isSwapped = false;
for (i = 0; i < len; i++) {
isSwapped = false;
for (j = 0; j < len; j++) {
if (arr[j] > arr[j + 1]) {
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
isSwapped = true;
}
}
if (!isSwapped) {
break;
}
}
return arr;
};