[알고리즘 | JS] sorting algorithm(정렬 알고리즘) - bubble sort

1. What is sorting? 

간단히 설명하자면 정렬 알고리즘이란 컬렉션(e.g. 배열)의 항목을 재배열하는 과정을 의미한다. 

• e.g.) 문자열을 하나 고른 후에 문자열 내의 각 문자를 정렬하는 것
• 정렬 알고리즘의 대표적인 종류들만해도 15가지가 넘는다. 인설션 소트(insertion), 퀵 소트(quick), 버블 소트(bubble), 머지 소트(merge), 힙 소트(heap), 기수 소트(radix sort) 셸 소트(shell)등등.. 여러가지 접근 방법이 존재한다. 

2. 왜 배워야 할까?

1. 정렬(sorting)이 프로그래밍에서 정말 흔하게 사용되기 때문이다. JS, 루비, 파이썬의 내장 정렬 메서드를 사용하고 있더라도, 거기에 어떤 알고리즘이 사용되는 지를 이해하는 것이 중요하다.
2. 데이터를 정렬할 수 있는 방법은 많고 우리가 살펴볼 각 알고리즘에는 장 단점이 존재하기 때문이다. 

가장 흔한 정렬 알고리즘의 종류로는 7개 정도를 비교하여 애니메이션으로 구현한 홈페이지가 있으니 참고하면 좋은 자료가 될 것이다. 이 사이트의 장점은 단지 7개의 소팅 알고리즘을 비교하는 것이 아니라 데이터의 상태에 따라서도 비교할 수 있다는 점이다. 

• 예시로 데이터가 거의 다 소팅되어있고 부분만 소팅되지 않은 컬렉션(nearly sorted data)에 해당 알고리즘을 적용했을 때도 비교하여 확인해볼 수 있다.
• 사이트 이름은 Sorting Algorithms Animations 이다. <-링크를 걸어두었다. 

---

자바스크립트의 내장 sort 메서드 

자바스크립트도 sort 메서드를 가지고 있다. -> 하지만, 예상대로 작동하지는 않는다.

 e.g) [영문 string을 담고 있는 배열].sort(); // A ~ Z 로 정렬한다.

하지만, [숫자를 담고 있는 배열].sort(); 를 했을 때에는 어떤 기준으로 정렬했는 지 알 수 없는 배열이 된다.

그 이유는 바로 Array.sort()의 기본 정렬 순서는 문자열 유니코드(unicode) 코드 포인트(code point)에 따르기 때문이다.

• 즉, 배열의 모든 항목이 문자열로 변환되고 해당 문자열의 유니코드 값이 선택되고 그 다음에 항목이 정렬된다는 

결국 애초에 문자열로 정렬을 시작하지 않는 한 원하는 결과를 얻을 수 없다는 것이다. 

해결방안은 sort에 인자로 비교함수를 만들어서 전달해주는 것이다.

 

이 비교함수는 음수를 반환하면 num1이 num2 앞에 온다. 반대로 양수를 반환하면 num2가 num1앞에 온다.

 function numberCompare(num1, num2) {
    return num1 - num2;
  }
  console.log([6, 5, 15, 10].sort(numberCompare)); //[ 5, 6, 10, 15 ]
  //* num1인 6에서 num2인 5를 뺐을 때, 양수를 return 하므로  num2인 5가 6보다 앞으로 오게 된다. 
  // 즉, 이를 통해서 내림차순 정렬이 가능하다.

• 내림차순으로 하고 싶다면 return 값을 음수로 만들어주면 된다. 즉, num2 - num1을 하면 된다. 

---

Bubble sort (버블 정렬)

- 버블 정렬의 개념은 배열을 가장 작은 숫자에서 가장 큰 숫자 순으로(오름차순) 정렬한다면 더 큰 숫자가 한 번에 하나씩 뒤로 이동하는 것이다. 

*시각적으로 파악하고 싶다면, VISUALGO 라는 사이트를 참고하면 좋을 것

 

1.버블 정렬의 작동 방식

버블 정렬은 별로 효율적이지 않다. -> 잘 사용되지 않는다. 

하지만, 효율이 좋지않는 소팅 알고리즘을 알게되면 다른 알고리즘과 비교하여 보기 좋다.

하지만 두각을 나타내는 분야가 존재하기 때문에 원리를 알아두는 것이 좋다.

 

루프를 돌면서 각 항목을 다음 항목(해당 항목의 오른쪽에 있는 항목)과 비교하는 것

그리고 해당 숫자가 더 크다면 교환(swap)을 한다. 기본적으로 어떤 항목이 더 크면 교환하고.. 이 과정을 반복한다. (오른쪽 항목보다 원래 항목이 더 크지않다면 교환하지 않는다.)

논리의 핵심은 루프를 돌면서 비교하고 swap을 호출하는 것이다. 

-> key point는 반복을 거듭함에 따라서 우리가 정렬해야하는 항목의 수가 감소한다.

-> 버블 소팅을 하게되면 해당 항목의 마지막 요소는 정렬되어 정렬되지 않은 항목에서 제외되기 때문?

 

[소트를 하기 전에 무조건 교환해야 한다.]

많은 정렬 알고리즘들이 스와핑 기능을 포함하고 있다. 

 

2. 버블 정렬의 시간 복잡도

• 일반적으로는 n제곱 == O(n^2) -> 중첩 루프가 있고, 대략적으로 비교하기 때문이다.
• 예외적으로, 데이터가 거의 정렬됐거나(nearly sorted data) 이미 정렬이 끝난 상태에서 noSwaps 변수가 있는 버전에서는 linear time에 더 가깝다. (최적화를 통해 linear time인 O(n))

3. 버블 정렬 예시: O(n^2) 

  //ES5
  function swap(arr, idx1, idx2) {
    let temp = arr[idx1];
    arr[idx1] = arr[idx2];
    arr[idx2] = temp;
  }

  //ES2015
  //심플해보이지만 가독성이 떨어지는 단점이 있다.
  //장점: 파일 크기와 파일이 얼마나 짧은 지 관심이 있는 사람은 아래의 코드를 사용하는 걸 추천
  const swap = (arr, idx1, idx2) => {
    // arr[idx1] 을 arr[idx2] 로 바꾸고 arr[idx2]를 arr[idx1]으로 바꾼다. 
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  };
  
  //chapGPT example
  function swap(a, b) {
    var temp = a;
    a = b;
    b = temp;
  }

  // Example usage
  var x = 10;
  var y = 20;
  console.log('Before swap: x =', x, 'y =', y);
  swap(x, y);
  console.log('After swap: x =', x, 'y =', y);

• 직접 swap함수를 구현하는 일은 드물지만 알아두면 좋다.

bubbleSortExample.js

// bubbleSort 만들어보기(최적화 되기 전)
// * 최적화 되기 전이라고 한 이유: 우선 마지막 요소인 숫자와 마지막에 존재하지않는 수 undefined가 비교되는 경우가 생기고
// * 한번의 swap가 생기면 마지막 요소는 이미 정렬된 수라 비교할 필요가 없는데 또 다시 비교에 들어간다.
// ? 여기서 불필요한 연산을 줄이려면? 한번의 swap이 발생하면 총4개의 요소에서 3개의 요소만 비교하는 식으로 비교 횟수를 줄여가는 것
{
  function bubbleSort(arr) {
    for (let i = 0; i < arr.length; i++) {
      for (let j = 0; j < arr.length; j++) {
        console.log(arr);

        if (arr[j] > arr[j + 1]) {
          //SWAP ->조건, 지금 대상이 비교대상보다 크다면 swap!
          let temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
        }
      }
    }
    return arr;
  }

  bubbleSort([25, 35, 29, 8]);
}

// 리팩터링 최적화전 bubbleSort 함수
{
  function bubbleSort(arr) {
    //for 루프의 조건을 바꿔준다. i의 초기값이 4로 시작하고 i가 1에 도달할때 종료, i를 감소시킨다.
    for (let i = arr.length; i > 0; i--) {
      // j는 0부터 시작하며 j는 i-1보다 작을때까지, j를 증가시켜준다.
      for (let j = 0; j < i - 1; j++) {
        console.log(arr, arr[j], arr[j + 1]);

        if (arr[j] > arr[j + 1]) {
          //SWAP ->조건, 지금 대상이 비교대상보다 크다면 swap!
          let temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
        }
      }
      console.log('----one pass complete-----');
    }
    return arr;
  }

  console.log('the answer: ', bubbleSort([25, 35, 29, 8, -4, 330]));
  /*
  [ 25, 35, 29, 8, -4, 330 ] 25 35
  [ 25, 35, 29, 8, -4, 330 ] 35 29
  [ 25, 29, 35, 8, -4, 330 ] 35 8
  [ 25, 29, 8, 35, -4, 330 ] 35 -4
  [ 25, 29, 8, -4, 35, 330 ] 35 330
  ----one pass complete-----
  [ 25, 29, 8, -4, 35, 330 ] 25 29
  [ 25, 29, 8, -4, 35, 330 ] 29 8
  [ 25, 8, 29, -4, 35, 330 ] 29 -4
  [ 25, 8, -4, 29, 35, 330 ] 29 35
  ----one pass complete-----
  [ 25, 8, -4, 29, 35, 330 ] 25 8
  [ 8, 25, -4, 29, 35, 330 ] 25 -4
  [ 8, -4, 25, 29, 35, 330 ] 25 29
  ----one pass complete-----
  [ 8, -4, 25, 29, 35, 330 ] 8 -4
  [ -4, 8, 25, 29, 35, 330 ] 8 25
  ----one pass complete-----
  [ -4, 8, 25, 29, 35, 330 ] -4 8
  ----one pass complete-----
  ----one pass complete-----
  the answer:  [ -4, 8, 25, 29, 35, 330 ]
  */
}

3-1. 버블 정렬 예시: O(n) 

 

• 우선 정렬하려는 데이터가 거의 다 정렬된 상태여야 한다.(nearly sorted). 
• swap의 상태를 체크하는 변수명을 만들고 boolean값을 루프에 지정한다. (e.g) noSwaps or isSwapped 등등..) 
• 조건문을 통해서 swap되지 않는 상태라면 break를 걸어 불필요한 연산을 하지않도록 끝낸다.

// bubbleSorting 최적화 ver
// * noSwaps 라는 변수를 만들어준다.
// swap이 일어나지않는다면 break를 걸어 루프밖으로 나가게 한다.
{
  function bubbleSort(arr) {
    let isSwapped;
    for (let i = arr.length; i > 0; i--) {
      isSwapped = false;
      for (let j = 0; j < i - 1; j++) {
        console.log(arr, arr[j], arr[j + 1]);
        if (arr[j] > arr[j + 1]) {
          let temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
          isSwapped = true;
          console.log('SWAP!');
        }
      }
      console.log('----one pass complete-----');
      if (!isSwapped) break;
    }
    return arr;
  }
  console.log(bubbleSort([1, 2, 3, 7, 5, 13, 14]));
}