[Algorithm log] BubbleSort

bubbleSort는 인접한 두 요소를 가지고 비교해서 정렬하는 정렬 알고리즘이다.

...

한 사이클을 돌면 이렇게 가장 큰 요소가 제일 뒤로 간다.

또 다음 싸이클을 돌면 요소는 10, 12, 13, 15, 16, 20으로 정렬이 되어있을 것이다.

이걸 정렬될 때까지 계속하는 것이다.

---

개인적으로 이런 정렬 알고리즘을 풀 때 반복문을 어떻게 구성하느냐가 핵심인 것 같다. 나는 항상 이론으로는 이해가 어렵지 않은데 코드로 옮기려고만 하면 너무 어려웠다. 지금도 뭐 다르진 않지만...

각설하고,

모든 요소만큼 사이클이 돌아야 하므로 반복문은 0 ~ 배열의 길이 - 1 까지는 돌아야 할 것 같고,

한 사이클당 반복은 인접한 요소들을 모두 확인하고 마지막 요소가 가장 크다는 것을 알고 있으니까

0 ~ 배열의 길이 - n번째 사이클 만큼은 돌아야 한다.

---

code

function bubbleSort(array) {
  for(let i=0; i<array.length-1; i++){  // 요소갯수만큼의 사이클
    for(let j=0; j<array.length-1-i; i++){  // 한 싸이클당 비교
      // 인접한 요소들을 확인한다.
      let temp;
      if(array[j] > array[j+1]){
        // 앞에요소가 더 크면 바꿔준다.
        temp = array[j];
        array[j] = array[j+1];
        array[j] = temp;
      }
    }
  }
  return array;
}

두 번째 For문에서 i 가 핵심이다. 밖에 있는 for문이 한번 돌면 배열의 가장 마지막에는 가장 큰 수가 들어있다는 것을 알기 때문에 그 부분에 반복을 빼준 것이다.

bubbleSort의 시간 복잡도는 n^2이다. 실제적으로 사용하기에는 무리가 있지만 for문을 어떻게 구성해야 하는지에 대한 공부를 할 수가 있었다.