[JavaScript 알고리즘] 정렬(sorting) - 1. Bubble Sort

정렬을 왜 배워야돼요?

- 정렬은 프로그래밍에서 매우 매우 흔한 작업입니다. 그래서 어떻게 작동하는 지 알 필요가 있어요.

- 정렬하는 데는 아주 많은 방법들이 있습니다. 그리고 장단점이 각각 다르죠.

 

학습 목표

bubble sort를 구현하자

selection sort를 구현하자

insertion sort를 구현하자

더 간단한 sorting algoritnm들을 왜 배워야 하는지를 이해하자.

 

근데 자바스크립트에 sort 메서드 있어요!

맞아요. 근데 항상 네가 원하는대로는 정렬 안해줄걸요?

 

특히 숫자array.sort()를 하면 사전순으로 정렬해버려요.

25가 4보다 앞에 와버리는 일이 생기는거죠.

 

하지만 걱정마세요!

Javascript 내장 sort 메서드는 comparator function을 인자로 받을 수 있어요.

function numberCompare(num1, num2) {
  return num1 - num2;
}

[6,4,15,10].sort(numberCompare);

function compareByLen(str1, str2) {
  return str2.length - str1.length;
}

["kim" "taeho", "is", "handsome"].sort(compareByLen);

이런 식으로요.

 

BubbleSort

BubbleSort는 사실 잘 안써요. 성능도 꾸져요.

근데 왜 배우냐고요?

이걸 배워야 다른 Sorting Algorithm들이 어떻게 얼마나 더 좋은지 알 수 있거든요.

그러니 집중!

https://visualgo.net/en/sorting

VisuAlgo - Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix)

sort과정을 시각적으로 보여주는 사이트입니다.

완전 이해 잘되니 꼭 보세요!

 

Bubble Sort는 인접한 요소들의 대소를 비교해서 조건에 맞으면 안바꾸고, 틀리면 바꾸는 방식으로 정렬을 진행합니다.

그래서 자리를 바꾸는 Swap이라는 행동이 필수적이죠.

많은 sorting algorithm들이 몇몇 종류의 swapping 기능들을 포함하고 있습니다.

 

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

// ES2015에선 이게 가능하네요
const swap = (arr, idx, idx2) => {
  [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
}

 

의사코드

변수 i부터 배열 끝까지 순회합니다. 

inner loop를 변수 j가  i-1이 될때까지 순회합니다.

arr[j]가 arr[j+1]보다 크다면, 두 요소를 swap합니다.

정렬된 배열을 return합니다.

 

구현

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

bubbleSort([37,45,29,8]);

이중 for문을 돌립니다.

inner loop를 보면 현재 요소가 다음 요소보다 크다면 자리를 바꿔요.

오름차순으로 정렬하는 거죠.

 

하지만 여기서 문제가 하나 있어요.

45가 2번 SWAP되어 [37, 29,8,45]일 때 45와 그 다음 undefined를 비교해버립니다. 

i와 j가 arr.length 보다 작을때까지 반복되니까 배열의 맨 끝에가서는 undefined와 대소를 비교해버려요.

버그는 나지 않지만 필요없는 동작을 하는거죠.

오이오이, 동작에 군더더기가 많아!

 

그래서 아래와 같이 코드를 수정해줍시다.

 

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

i를 arr.length에서 시작해서 0보다 클 때까지 역방향으로 반복시키는 거에요

그리고 j는 i-1보다 작을때까지 반복해서 마지막의 군더더기 동작을 제거해줍니다.

 

ES2015 버전으로 깔끔하게 마무으리 해줍시다.

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;
}

 

??? : "허점 투성이군"

잠깐! 최적화합시다!

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;
}

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

위와 같이 거의 다 정렬된 배열을 정렬한다고 해봅시다.

8이 맨 끝에로 갔음에도 i는 7, 6, 5, ... , 1까지 순회를 해요.

SWAP이 전혀 일어나지 않는데도 말이죠.

배열이 커지면 커질 수록 쓸데 없는 동작이 많아지겠죠?

너란 녀석, 아직도 허점 투성이군!

 

그래서 우리는 noSwaps라는 조건을 만들어볼거에요.

 

function bubbleSort(arr) {
  let noSwaps;

  const swap = (arr, idx1, idx2) => (
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  );
  
  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;
}

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

inner loop 바깥 루프에 noSwaps를 true로 설정합니다.

inner loop 안에서 swap이 일어나면 noSwaps를 false로 만들어줍시다.

inner loop가 끝나고 새로운 i로 동작할 때는 noSwaps가 다시 true로 되겠죠?

만약 그 Inner loop 안에서 swap이 일어난다면 break할 기회가 안만들어지면서 동작이 계속되는거고요,

swap이 없다면 비로소 if(noSwaps) 조건이 만족되면서 군더더기를 없애고 동작을 종료할 수 있습니다.

 

필요 없는 동작을 하고 싶지 않을 때 이러한 조건을 사용하면 되겠군요!

좋은 테크닉을 배운 것 같습니다.