알고리즘 - 버블 정렬(Bubble Sort) / 버블 정렬 구현

정렬이란?

---

정렬은 객체들이 나열된 순서를 어떤 논리적인 순서에 맞도록 바꾸는 작업이다. 예를 들면 숫자들의 순서를 오름차순으로 변경하거나 내림차순으로 바꾸는 등의 일을 할 수 있다.

 

📌 정렬 알고리즘을 배워야 하는 이유.

1. 서로 다른 알고리즘 간의 비교하는 방법을 배울 수 있다.
2. 정렬 알고리즘에 적용한 기술들을 다른 문제에도 유사하게 활용할 수 있다.
3. 정렬을 먼저 수행하면 효율적으로 문제를 해결할 수 있거나 해결 불가능한 문제도 가능하게 해준다.

 

버블 정렬?

---

각 패스마다 정렬되지 않은 값 중 가장 큰 값을 의미하는 버블이 올바른 위치로 이동하게 되면서 정렬이 수행되는 알고리즘이다. 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식이라고 생각하면 쉽다.

 

 

📌 버블 정렬의 동작 순서.

1. 배열 내에서 연속된 두 항목을 가리킨다.
   • 처음에는 배열의 첫 번째 원소부터 시작한다.
2. 두 항목의 순서가 뒤바뀌어 있으면 교환한다.
   • 순서가 바뀌어 있다는 것은 왼쪽 값이 오른쪽 값보다 크다는 것을 의미한다.
3. 가리키는 포인터를 오른쪽으로 한 셀씩 옮긴다.
4. 배열의 끝까지 혹은 이미 정렬되어 있는 값까지 1-3 단계를 반복한다.
   • 한 번의 패스스루가 끝났다는 것을 의미한다.
   • 패스스루란 1-3단계를 진행하면서 배열의 끝까지 값을 하나씩 가리킨 것이다.
5. 두 포인터를 배열의 처음 두 값으로 옮겨서 1-4단계를 실행한다.
   • 교환이 일어나지 않을 때까지 패스스루를 반복한다.

 

📌 버블 정렬의 효율성

버블 정렬 알고리즘은 두 가지 단계를 포함하고 있다.

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

 

📌 최악의 경우

버블 정렬의 가장 최악의 경우는 오름차순 정렬을 하려고 하는데 배열이 내림차순으로 정렬되어 있을 때이다. 원소 N개가 있을 때 (N-1) + (N+2)+(N+3) .... +1번의 비교를 수행하게 된다. N=5일 때 내림차순으로 정렬되어 있었다면 10번의 교환이 일어난다. 10번의 비교와 10번의 교환이 일어나기 때문에 총 20단계가 걸린다. 만약에 N=10이라면 9+8+7+6+5+4+3+2+1 = 45번의 비교와 45번의 교환이 일어난다.

데이터 원소 N개	최대 단계수
5	20
10	90
20	380
40	1560
80	6320

 

이 표를 보면 원소 수가 증가할수록 단계 수가 기하급수적으로 늘어나는 것을 확인할 수 있다. N이 증가할 때마다 대략 N^2만큼 늘어나는 것을 알 수 있다. 값이 N개이기 때문에 버블 정렬에는 N^2단계가 필요하고 최악의 경우 효율성은 O(N^2)이다.

 

📌 최선의 경우

버블 정렬의 최선의 경우는 이미 원하는 대로 정렬되어 있는 것이다. 버블 정렬에서는 한 번도 교환이 일어나지 않으면 이미 정렬되었다는 것을 알 수 있다. 그래서 적어도 N-1번만큼은 비교를 해봐야 이미 정렬되어 있다는 것을 알게 된다. 그래서 버블 정렬에서 최선의 경우 효율성은 O(N)이다.

 

📌 평균적인 경우

버블 정렬의 평균적인 경우에는 N-1만큼 진행되던 교환이 평균적으로 일어나니까 1/2로 계산해도 결국 O(N^2)가 나온다. 버블 정렬의효율성을 살펴보면 최선의 경우 O(N), 평균의 경우 O(N^2), 최악의 경우 O(N^2)이다.

 

	최선의 경우	평균의 경우	최악의 경우
버블 정렬	O(N)	O(N^2)	O(N^2)

 

버블 정렬은 일반적으로 상당히 느린 알고리즘으로, 크기가 큰 데이터 세트를 정렬해야 하는 상황에서는 다른 효율적인 정렬 알고리즘을 사용하는 것이 좋다.

 

Ex.

// array = [4,2,1,5,3]
const bubbleSort = (array) => {
  for(let i = 0; i <= array.length; i++){ //정렬해야 하는 배열 크기만큼 비교
    let swapped = false; 

    for(let j = 0; j < array.length - i; j ++){
      if(array[j] > array[j + 1]){
        const temp = array[j];

        array[j] = array[j + 1];
        array[j + 1] = temp;
        swapped = true; 
      }
    }

    if(!swapped) break; // 한 번도 교환이 일어나지 않았으면 for문 종료
  }

  return array; //결과 [1,2,3,4,5]
};