[javascript] 버블정렬

버블정렬은 큰 값을 찾아 뒤에 위치시키는 방법으로 정렬하는 방식이다.
물방울이 올라가는 것 같다고 해서 붙여졌다는데 사실 그건... 딱히 와닿지 않는 것 같음ㅎ

1번 풀이

내가 문제를 보고 그냥 자연스럽게 가장 먼저 친 코드는 중복for문이었다.
이 문제 역시 정처기 공부하면서 많이 본 문제이기 때문에 생각도 안하고 그냥 손이 침..
가장 마지막 테스트를 제외하면 모두 통과가 되었다.

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

2번 풀이

알고리즘 강의를 듣고 고친 코드.

1. 데이터교환을 했는지 여부를 검사한다.

더이상 데이터 교환이 없다면 정렬을 마친 것이니 반복문을 그만 돌린다.

2. i와 j가 아니라 j와 j+1을 비교한다.

이게 훨씬 이해가 잘 가는게, 버블정렬은 바로 앞뒤 숫자를 비교하는거니까.

3. arr.length만큼이 아니라 정렬되기 전까지의 인덱스만큼만 비교한다.

큰 수를 뒤로 보내니 arr.length - 1씩 비교해야 할 수가 줄어든다.
굳이 arr.length만큼 할 필요가 없다.

let bubbleSort = function (arr) {
  for (let i = arr.length; i > 0; i--) {
    noSwaps = true;
    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;
        noSwaps = false;
      }
    }
    if(noSwaps) break;
  }
  return arr;
};