버블 정렬 Bubble Sort

처음으로 소개드릴 알고리즘은 정렬 중에서도 버블 정렬입니다. 버블이라는 어원은 컵에 액체를 따르면 액체 보다 가벼운 공기 방울(버블)이 컵위로 떠오른다는 점에서 착안하여 버블 정렬이라는 이름이 붙게 되었습니다.

---

1. 버블 정렬

버블 정렬은 인접한 두 요소의 대소 관계를 비교해서 정렬합니다. 버블 정렬은 가장 간단한 형태의 정렬이며 시간복잡도는 O(n^2)로 요소가 많아질수록 느립니다.

다음과 같은 배열을 오름차순 버블 정렬해보겠습니다.

 

이렇게 양옆의 요소들끼리 비교하여 요소의 크기가 작으면 앞으로 보내고, 크기가 크면 뒤로 보냅니다.

이 경우에는 배열을 1회 순회하는 동안 버블정렬이 완료되었지만 1회 순회 했음에도 정렬되지 않는 경우가 있습니다. 다음 배열을 보면 1회 수행했음에도 완벽하게 정렬되지 않습니다.

이렇게 정렬에서 1회 순회 하는 것을 패스라고 하는데 1회 패스당 1개의 인덱스가 정렬됩니다. 그래서 버블 정렬로 모든 배열을 정렬하려면 배열의 크기가 n일 때 n-1회 만큼 패스를 반복해야합니다.

 

 

2. 버블 정렬 구현

요소1 = 요소2
요소2 = 요소1

이렇게 바꿔치기 할 수 있다면 편하겠지만 첫 줄을 실행하는 순간 요소1은 요소2와 같아지므로 불가능합니다. 그래서 우리는 임시 변수를 하나 더 만들어서 이용해야 합니다.

임수 변수에 요소1의 내용을 저장한 후 요소2의 내용을 요소1에 덮어 씌웁니다. 그리고 임시 변수에 저장된 요소1의 값을 요소2에 넣어주면 두 변수간의 요소 변환이 가능합니다.

temp = elem1;
elem1 = elem2;
elem2 = temp;

 

이제, 서론에서 소개한 원리와 방금 소개한 정렬 법을 이용해서 구현해보겠습니다.

const bubbleSort = (arr) => {
    for (let i = 0; i < arr.length; i++) {	//n-1회 만큼 패스 수행
        for (let j = arr.length; j > i; j--) {	//인덱스
            if (arr[j - 1] > arr[j]) {	//이전 요소가 현재 요소보다 크면
                let temp = arr[j - 1];	//버블 정렬 실행
                arr[j - 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
};

 

참고로 오름차순으로 정렬했는데, 조건문의 내용만 바꿔주면 내림차순으로도 정렬이 가능합니다.

---

https://github.com/Bam-j/algorithm-study/blob/main/study-code/sort/bubble-sort.js

GitHub - Bam-j/algorithm-study: 블로그 알고리즘 정리 포스트 코드 수록 + 코딩 테스트 코드 수록