CS) 정렬 - 버블 정렬과 효율성

김명성·2023년 6월 5일

버블 정렬

버블 정렬은 정렬 알고리즘 중에서 매우 기본적인 알고리즘에 속한다.

버블 정렬의 진행 순서

1-1. 배열 내에서 연속된 두 항목을 가르킨다.(포인터 설정)
const arr = [2,1,3,5,7,4]
첫 번째 원소(2)부터 시작하여 그 다음 원소(1)를 비교한다.

1-2. 왼쪽 값이 오른쪽 값보다 크면 두 항목을 교환한다.
(오른쪽 값이 크다면 아무런 행동도 하지 않고 다음 단계로 이동한다.)

1-3. 포인터를 오른쪽으로 한 칸씩 옮긴다.

2-1. 이제 포인터는 2와 3을 가르킨다.

2-2. 왼쪽 값이 오른쪽 값보다 작기에 행동하지 않는다.

2-3. 포인터를 오른쪽으로 한 칸씩 옮긴다.

3-1. 이제 포인터는 3과 5를 가르킨다.

배열의 끝까지 또는 이미 정렬된 값까지 1단계부터 3단계까지 반복한다.
배열의 끝까지 진행하였다면 패스 스루가 1회 진행된 것이라 한다.
위 예시에서 패스 스루의 1회 진행 결과는 [1,2,3,5,4,7]이다.

이제 포인터를 다시 배열이 처음 두 값으로 옮겨서 새로운 패스 스루를 실행한다.
교환이 일어나지 않는 패스스루가 생길 때까지 패스 스루는 계속된다.

[1,2,3,5,4,7]의 결과를 보면
이 알고리즘을 버블 정렬이라 부르는 까닭을 알 수 있다.
각 패스스루마다 정렬되지 않은 값 중 가장 큰 값, "버블"이 올바른 위치로 가게 되기 때문이다.

버블 정렬을 자바스크립트로 구현한 예시


const bubbleSort = (list) => {
  const lt = list.length;
  for(let i = 0; i < lt; i++){ // 총 단계 수(패스 스루의 횟수)
    for(let j = 0; j < lt - i; j++) { // 패스 스루에 종속된 세부 단계 수
      // 왼쪽의 값이 오른쪽의 값보다 크다면
      if(list[j] > list[j + 1]) {
      // 두 값의 위치를 바꾸어준다.
        [list[j], list[j + 1]] = [list[j + 1], list[j]];
      }
    }
  }
  return list;
}

console.log(bubbleSort([1,2,3,5,7,4])); // [1,2,3,4,5,7]

버블 정렬의 효율성

버블 정렬 알고리즘은 두 가지 중요한 단계를 포함한다.

비교 : 어느 쪽이 더 큰지 두 수를 비교한다.
교환 : 정렬하기 위해 두 수를 교환한다.

예시로 든 배열의 원소는 6개이고, 첫 번째 패스 스루에서 두 수의 비교를 5번, 두번째 패스 스루에서는 4번 진행했다.
요약하자면 각 패스 스루마다 직전의 비교 대상 원소의 수에 1을 뺀 수가 비교에 필요하며 예시에서는 총 15(5+4+3+2+1)번의 비교가 필요했다.

버블 정렬은 말 그대로 정렬이기에 비교만 한다고 해서 정렬이 되는 것이 아니다. 비교를 한 뒤에 교환이 진행되야 한다.

만약 배열이 내림차순으로 정렬된 최악의 시나리오라면 비교할 때마다 교환이 진행되야한다. 이러한 시나리오에서는 비교가 15번, 교환이 15번 일어나 총 30단계를 거쳐야 정렬이 된다.