📋 버블 정렬 알고리즘

버블 정렬은 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.

작동 방식은 옆에 있는 데이터와 비교하여 더 작은 값을 점점 앞으로 보내는 방식이다.

사실 버블정렬은 그렇게 효율적인 정렬방법이라고 할 순 없지만 다른 정렬 알고리즘에 비해서 구현하기 쉽다는 장점이 있다.

---

📌 1. 버블 정렬 작동 방식

알고리즘 비주얼화 해주는 사이트
https://visualgo.net/en/sorting

위에서 말했듯이 옆의 값과 비교해 더 작은 값을 점점 더 앞으로 보내며 진행한다.

---

📌 2. 버블정렬 구현

function bubbleSort(arr){
  for(var i = arr.length; i > 0; i--){
    for(var j = 0; j < i - 1; j++){
      if(arr[j] > arr[j+1]){
        var temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;         
      }
    }
  }
  return arr;
}

내게 가장 익숙한 언어인 자바스크립트로 구현해보았다.

이 방식은 제대로 작동하기는 하지만, 만약 정렬이 완료된 상태라도 계속해서 for문이 돌아간다.

이를 해결하기 위해 어떻게 할 수 있을까?

나는 noSwap이라는 변수를 만들어 swap이 실행된다면 noSwap이 false가 되고,
swap이 실행되지 않는다면 noSwap이 true가 되게끔 해서 정렬을 멈추는 방식으로 구현해보았다.

솔루션 적용

function bubbleSort(arr) {
  let noSwap;
  for (var i = arr.length; i > 0; i--) {
    noSwap = true;
    for (var j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        var temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        noSwap = false;
      }
    }
    if (noSwap) break;
  }
  return arr;
}

이렇게 let noSwap; 을 통해 noSwap을 정의해주고
만약 j 루프에서 스왑을 하지 않았다면,
i 루프에서 정의된 noSwap이 true기 때문에 if (noSwap) break;에 걸려 루프가 멈추게 된다.

---

📌 3. 버블 정렬의 시간 복잡도

일반적으로는 O(n^2)로 상당히 비효율적이다.

하지만 noSwap 변수를 적용한 버전에 거의 정렬된 데이터를 넣으면 O(n)에 가깝다고 볼 수 있다.