버블 정렬

정렬 알고리즘

What is sorting?

Sorting is the process of rearranging the items in a collection so that the items are in some kind of order.

Why do we need to learn this?

• Sorting is an incredibly common task, so it’s good to know how it works.
• There are many differnt techniques have their own advantages and disadvantages.

Sorting Algorithms Animations

⇒ 어떤 정렬이 무조건 절대적으로 빠른것은 아니다!! 데이터가 현재 어떤 상태인지에 따라 느릴수도 빠를수도 있다. 그래서 각각 장단점이 있고, 그걸 이해할 가치가 있다.

버블, 선택, 삽입 정렬 ⇒ 기본적인 정렬 알고리즘

기본 내장 자바스크립트 정렬

sort()

기본 정렬 순서는 문자열 유니코드, 코드 포인트에 따른다.

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

내장 정렬 메소드는 선택적 비교 함수를 인자로 전달받는다. 이 함수를 사용해서 자스에 우리가 원하는 정렬 방식을 알릴 수 있다.

• 함수가 음수를 반환하면 자스는 a가 b 앞에 온다고 결정한다. 즉, 오름차순 정렬! 양수를 반환하면 a가 b 뒤에 온다. 내림차순 정렬! (a는 첫번째 인자, b는 두번째 인자를 뜻한다.)

버블 정렬 : 개요

버블 정렬은 효율적이지 않다. 흔히 사용되지도 않고! 어떻게 사용하는지 알면 재밌는 알고리즘이다. 몇 가지 최적화를 할 수 있다. 그래서 다루기 좋은 주제이다.

작동 방식 : 루프를 돌면서 각 항목을 다음 항목과 비교한다. 다음 항목보다 더 크면 교환한다.

BubbleSort

A sorting algorithm where the largest values bubble up to the top!

기억해야 할 점은 반복을 거듭함에 따라 우리가 정렬해야 하는 항목의 수가 감소한다는 점이다!!

버블 정렬 : 구현

루프가 실행되는 동안 끝부분이 정렬된다. 그래서 매번 끝까지 비교를 할 필요는 없다. 하지만 최적화되지 않은 솔루션의 경우 에는 코드가 매번 끝까지 비교와 교환을 실시한다.

루프가 실행되는 동안 배열을 정렬하고 있으니까 비교 횟수를 줄이는거다.

// UNOPTIMIZED VERSION OF BUBBLE SORT
function bubbleSort(arr) {
  for (var i = arr.length; i > 0; i--) {
    for (var j = 0; j < i - 1; j++) {
      console.log(arr, arr[j], arr[j + 1]);
      if (arr[j] > arr[j + 1]) {
        var temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

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

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

버블 정렬 : 최적화

// Optimized BubbleSort with noSwaps
function bubbleSort(arr){
  **var noSwaps;**
  for(var i = arr.length; i > 0; i--){
    **noSwaps = 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;
        **noSwaps = false;**         
      }
    }
    **if(noSwaps) break;**
  }
  return arr;
}

bubbleSort([8,1,2,3,4,5,6,7]);

빅오 복잡도

일반적으로는 n제곱이다. 왜냐하면 중첩 루프가 있고, 대략적으로 비교를 하기때문이다!

그러나 데이터가 거의 정렬됐거나 이미 정렬이 끝난 상태에서 noSwaps 변수가 있는 이 신규 버전을 사용할 때는 선형 시간에 더 가깝다.