거품정렬은 가장 간단한 정렬 알고리즘이다. 거품 정렬은 전체 배열을 순회하면서 항목이 다른 항목보다 큰 경우 두 항목을 교환하는 방식이다. 이 방식이 거품이 밀려 올라가는 것과 같은 모습이라고 해서 거품 정렬이라는 이름이 붙여졌다. 아래는 거품 정렬의 코드이다.
// swap 함수는 두 배열의 인덱스의 값을 바꾸는 함수임.
const swap = (array, index1, index2) => {
let temp = array[index1]; // 바뀔 것을 대비하여 값 저장
array[index1] = array[index2];
array[index2] = temp;
}
const bubblesort = array => {
for (let i=0;i<array.length;i++) {
for (let j=0;j<=i;j++) {
if (array[i] < array[j]) {
swap(array,i,j)
}
}
}
return array;
}
이 코드의 가장 큰 문제점은 배열의 거의 모든 짝을 비교해서 비효율적이라는 것이다. 게다가 시간복잡도가 O(n^2)이기 때문에 배열의 양이 많아질수록 시간이 기하급수적으로 증가한다. 따라서 이미 정렬이 되어있는 경우에는 반복을 멈추는 작업을 추가하면 좋다. 아래는 효율적 거품 정렬이다. break를 걸기 위하여 코드를 살짝 수정하였다.
const swap = function(idx1, idx2, arr) {
let temp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = temp;
}
const bubbleSort = function (arr) {
// TODO: 여기에 코드를 작성합니다.
for (let i=0;i<arr.length;i++) {
let swaps = 0;
for (let j=0;j < arr.length - 1 - i;j++) {
if (arr[j] > arr[j+1]) {
swaps++
swap(j,j+1,arr)
}
}
if (swaps === 0) break;
}
return arr
};
const arr = [1, 2, 21, 43, 100, 100, 82, 6]
console.log(bubblesort(arr));