30Dec2019 TIL

Today I learned : 

• bubble sort algorithm & Time complexity 

 

---

Bubble sort는 데이터를 규칙있게 배열하는 알고리즘의 한 방식이다. 지난 toy 문제 중 bubblesort 구현한 적이 있다. 함수 이름에 담긴 출제자의 의도와 다른 방식으로 문제를 해결했기 때문에, 이번엔 출제자의 의도에 맞게 bubblesort를 구현해보고자 한다. 더불어 bubble sort로 나열하게 될 경우 시간 복잡도는 어떻게 되는지도 살펴볼 예정이다.

 

나의 생각

우선, 출제자의 의도를 무시한 채, 배열의 엘리먼트를 오름차순으로 나열한 나의 코드는 다음과 같다. 배열 내 최소값을 찾고, 새 배열에 담은 후, 해당 엘리먼트는 삭제한다 -> 배열 내 최솟값을 찾고....(반복)하는 식으로 오름차순을 구현했다. 

 

var bubbleSort = function(array) {
  let result = [];
  let recurse = function(arr) {
    if (!arr.length) return result; //base : 배열 값이 0 이면 재귀 끝
    if (arr.length) {
      let findMin = arr => Math.min(...arr); //배열 내 최소값을 찾는 함수
      let min = findMin(arr); //최소값 변수 담기
      let idx = arr.indexOf(min); //최소값 인덱스 찾고 -> 배열에서 삭제
      result.push(min);
      arr.splice(idx, 1);
      return arr.length === 0 ? result : recurse(arr);
    }
  };
  recurse(array);
  return result;
};

 

그렇다면, 출제자가 의도한 bubble sort는 어떤 모습일까? 

An example of bubble sort. Starting from the beginning of the list, compare every adjacent pair, swap their position if they are not in the right order (the latter one is smaller than the former one). After each iteration, one less element (the last one) is needed to be compared until there are no more elements left to be compared. (출처 : 위키피디아)

 

즉, 인접한 배열의 엘리먼트 끼리 크기를 비교한 후 결과에 따라 배열의 순서를 바꾸는 작업을 더 이상 바꿀 작업이 없을 때까지 반복한다. 반복과 재귀를 통해 해당 작업을 반복해주었고, 더 이상 바꿀 작업이 없을 때 재귀를 멈추었다. 나의 코드는 다음과 같다.

 

var bubbleSort = function(array) {
  function recurse(array) {
    let sum = 0;
    for (let i = 0; i < array.length - 1; i++) {
      if (array[i] > array[i + 1]) {
        let a = array[i + 1];
        array[i + 1] = array[i];
        array[i] = a;
        sum++;
      }
    }
    return sum === 0 ? array : recurse(array);
  }
  return recurse(array);
};

 

bubble sort의 시간 복잡도는 어떠할까?

Although bubble sort is one of the simplest sorting algorithms to understand and implement, its O(n^2)complexity means that its efficiency decreases dramatically on lists of more than a small number of elements. Even among simple O(n^2) sorting algorithms, algorithms like insertion sort are usually considerably more efficient. (출처 : 위키피디아)

bubble sort는 O(n^2)의 시간 복잡도를 가지며, 나열해야할 엘리먼트가 많아질 수록 더욱더 복잡한 시간 복잡도를 가지게 된다. 한 Owen Astrachan 학자를 비롯한 연구자들은 해당 소팅은 더이상 가르치지 않아야 한다고 주장하기까지 하니, 가급적 해당 알고리즘은 이론으로만 알고 있는 것이 좋을 것 같다.