[JavaScript] Bubble Sort

OROSY·2021년 6월 15일

Bubble Sort JavaScript TIL udemy

Algorithms

목록 보기

29/38

Bubble Sort

지금부터는 정말 중요한 정렬 알고리즘에 대해 알아보도록 하겠습니다. 이전 시간에 배웠던 검색 알고리즘은 배열이 모두 정렬이 되어있다는 가정 하에 배운 알고리즘이었습니다.

그러나 정렬되지 않은 데이터는 검색이 매우 비효율적이므로 반드시 정렬이 선행되어야 합니다. 이러한 정렬의 첫 번째 예시인 버블 정렬에 대해 알아봅시다.

1. Bubble Sort

버블 정렬은 배열 데이터를 두 개씩 비교하는 정렬 방법입니다. 예시를 들어서 살펴보도록 할까요? 먼저 버블 정렬에 대해 본격적으로 배우기 전에 직접 눈으로 정렬이 진행되는 과정을 확인하면 더욱 쉽게 이해할 수 있습니다.

visualgo라는 사이트에서 이를 확인해보실 수 있으니 꼭 직접 눈으로 확인하시기 바랍니다. 그럼 본격적으로 버블 정렬에 대해 살펴봅시다.

[29, 14, 10, 37, 21]

위와 같이 총 5개로 이루어진 배열 데이터입니다. 보시다시피 정렬이 되어있지 않기 때문에 버블 정렬을 통해 오름차순으로 데이터를 정렬해보도록 하겠습니다.

[29, 14, 10, 37, 21] ⇒ [14, 29, 10, 37, 21]

먼저 앞의 두 데이터를 비교하여 버블 정렬을 진행하면, 위와 같이 배열이 바뀌었습니다. 그리고 배열의 마지막까지 정렬을 진행해봅시다.

[29, 14, 10, 37, 21] ⇒ [14, 29, 10, 37, 21]

[14, 29, 10, 37, 21] ⇒ [14, 10, 29, 37, 21]

[14, 10, 29, 37, 21] ⇒ [14, 10, 29, 37, 21]

[14, 10, 29, 37, 21] ⇒ [14, 10, 29, 21, 37] # 1단계 끝!

5번째의 배열 데이터를 버블 정렬을 진행해보았습니다. 이 결과에서 알 수 있는 것은 무엇일까요? 첫 번째로는 아직 배열의 정렬이 모두 완료되지 않았다는 점입니다. 그리고 또한 정렬을 통해 마지막에 있는 숫자가 가장 큰 숫자가 되었다는 점입니다.

결국 버블 정렬은 가장 큰 숫자부터 정렬을 하게 하는 방법이라 할 수 있습니다. 그렇다면 한 단계 더 정렬을 진행보도록 하겠습니다.

[14, 10, 29, 37, 21] ⇒ [10, 14, 29, 21, 37]

[10, 14, 29, 21, 37] ⇒ [10, 14, 29, 21, 37]

[10, 14, 29, 21, 37] ⇒ [10, 14, 21, 29, 37] # 2단계 끝!

이처럼 한 단계를 더 진행하였고, 이번에는 오름차순으로 예쁘게 정렬이 완료된 것을 확인할 수 있습니다. 첫 번째와 다른 점은 마지막 데이터는 정렬이 완료된 것을 알고 있기 때문에 1번이 감소된 총 3번으로 정렬이 완료됩니다. 그렇다면 이후에는 2번이 되겠군요.

그러나 여기서 정렬이 끝나지는 않습니다. 이유는 무엇일까요?

이는 우리는 정렬이 완료된 것을 눈으로 보고 확인할 수 있지만, 컴퓨터는 그럴 수 없습니다. 이를 위해 원래의 경우에는 2번째의 배열 데이터가 정렬이 완료될 때까지 반복이 되어야 합니다.

[10, 14, 29, 21, 37] ⇒ [10, 14, 21, 29, 37]

[10, 14, 29, 21, 37] ⇒ [10, 14, 29, 21, 37] # 3단계 끝!

[10, 14, 29, 21, 37] ⇒ [10, 14, 21, 29, 37] # 4단계 끝!

이처럼 배열의 첫 번째와 두 번째의 데이터가 정렬이 완료될 때까지 반복이 되어야합니다. 5개의 배열 데이터를 정렬하기 위해서는 최대로 총 10번(4번 + 3번 + 2번 + 1번)이 소요됩니다. 이것이 버블 정렬의 시간 복잡도가 되겠네요.

그렇다면 이를 코드로 구현을 해보도록 하겠습니다.

bubbleSort

function bubbleSort(arr) {
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]
  };
  
  for (let i = arr.length - 1; i > 0; i--) {
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j+1]) {
      	swap(arr, j, j+1);
      }
    }
  }
  return arr;
}

먼저 정렬을 진행하기 위해서는 배열의 두 데이터의 자리를 서로 바꿔주는 함수가 필요하겠죠? 이것이 swap이라는 변수에 저장한 함수입니다.

그리고 본격적으로 반복문을 이용하여 정렬을 진행해주어야 합니다. 위의 내용으로는 이해하기가 쉽지 않기 때문에 아래의 표를 통해 보도록 하겠습니다. 먼저 두 개의 변수인 i와 j를 통해 이를 구현해야합니다.

i	j	j + 1
4	0	1
4	1	2
4	2	3
4	3	4
3	0	1
3	1	2
3	2	3
2	0	1
2	1	2
1	0	1

위에서 이야기한 것처럼 총 5개의 배열 데이터는 한 번씩 줄어드는 총 4단계의 정렬이 필요합니다. 4단계는 i를 통해 나타내줍니다.

그리고 j는 실제로 정렬로 swap 함수가 진행될 수 있도록 합니다. 이를 위해서는 j와 j+1이 필요합니다. 이 두 숫자를 비교하여 arr[j]이라는 앞의 숫자가 더 크다면 뒤의 숫자와 바꿔주면 되겠죠?

for (let i = arr.length - 1; i > 0; i--) {
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j+1]) {
      	swap(arr, j, j+1);
      }
    }
  }

이를 코드로 구현한 것이 위와 같으며 마지막은 위의 함수를 통과한 배열을 반환하기만 하면 됩니다. 하지만 이 코드는 최적화가 진행되기 전의 코드입니다. 예를 들어, 모두 정렬이 된 배열 데이터라고 한다면 이렇게 모든 과정을 끝까지 진행해야한다는 것은 시간 낭비일 것입니다.

이를 해결하기 위해 위 코드의 최적화를 진행해보도록 하겠습니다.

bubbleSort Optimization

function bubbleSort(arr) {
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  };

  let noSwaps;

  for (let i = arr.length; i > 0; i--) {
    noSwaps = true;
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
        noSwaps = false;
      }
    }
    if (noSwaps) break;
  }
  return arr;
}

noswaps라는 변수를 통해 코드를 쉽게 최적화하였습니다. 기본적으로 해당 변수에 true를 입력한 상태에서 i의 단계에 따라 swap의 진행 여부에 대해 검사하도록 합니다. swap이 진행된다면, 이 변수에 false를 입력하여 반복문을 계속하여 진행합니다.

그러나 swap이 한 번도 진행되지 않았다면, 이를 확인하고 반복문을 끝내버리도록 합니다. 그렇다면 이제 버블 정렬의 Big O notation에 대해 알아봅시다.