문제 : bubbleSort

버블정렬 알고리즘을 구현하세요.

let output = bubbleSort([2, 1, 3]);
console.log(output); // --> [1, 2, 3]

Advanced : 위에서 설명된 알고리즘 1~3의 과정 중 어떤 요소도 위치가 바뀌지 않은 경우, 배열이 정렬된 상태라는 것을 알 수 있습니다. 이 점을 활용해서 수행 시간을 단축할 수 있도록 코드를 수정하세요.

문제의 접근

버블 정렬은 누구나 개념만 이해하면 쉽게 구현이 가능하다.

• 첫 번째, 두 번째 숫자 비교 후 큰수를 두번째 자리에 배치
• 두 번째, 세 번째 숫자 비교 후 큰 수를 세번째 자리에 배치 -> 끝까지 실행
• 위 과정을 문자열 수 만큼 실시해준다.

위 과정은 제일 큰 숫자를 오른쪽으로 보내고, 그 다음 큰 숫자를 또 오른쪽으로 보내면서 모든 숫자를 이런 형식으로 검사해서 오른쪽에 차곡차곡 정렬하면 된다.

const bubbleSort = function (arr) {
 // TODO: 여기에 코드를 작성합니다.
 for(let i = 0; i < arr.length; i++){
   for(let j = 0; j < arr.length - 1 - i; j++){
     if(arr[j] > arr[j+1]){
       let swap = arr[j];
       arr[j] = arr[j+1];
       arr[j+1] = swap;
     }
   }
 }
 return arr;
};

위 코드를 실행한다면 문자열의 길이가 길면 길어질 수록 오랜시간이 걸려서 정렬'은' 완수한다.

Advanced

그렇다면 앞서 작성한 코드는 효율적인 코드가 아닌 것이다. 애당초 버블 정렬은 시간복잡도가 높아서 효율적인 정렬이 아니라고 알고 있다. 그렇지만 이 버블 정렬을 조금이나마 효율적으로 만들기 위해서는 이미 정렬이 완성된 배열은 더 이상 버블 정렬을 실행 시키지 않으면 된다.

const bubbleSort = function (arr) {
  // TODO: 여기에 코드를 작성합니다.
  for(let i = 0; i < arr.length; i++){
    let swap;
    for(let j = 0; j < arr.length - 1 - i; j++){
      if(arr[j] > arr[j+1]){
        swap = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = swap;
      }
    }
    if(!swap){
      break;
    }
  }
  return arr;
};

바꿀 때 필요한 swap이라는 변수는 for문안에 if문을 통과 했는지 안했는지 확인 하기에 적합하다. 때문에 버블을 한 번 돌기 전에 swap을 선언만 해주고 값이 할당되지 않는다면 이미 정렬이 완성된 것이기 때문에 더 이상 버블을 실행해줄 필요가 없다.

문제를 통해 생각해 볼 것

버블 정렬은 항상 말만 들어왔고 효율적이지 않다고 해서 배울 필요가 없다고 생각했다. 하지만 이렇게 한번 직접 구현해봄으로 버블 정렬이 왜 효율적이지 못한지 알 수 있었고 구현 과정을 통해 생각하는 방법을 더 늘릴 수 있었다.