Algorithm 15 : bubbleSort

설명

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다.

• 버블정렬이란?
  옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내는 알고리즘이다.
  배열의 왼쪽부터 2개씩 요소를 비교하며 오름차순으로 정렬하는데 특징은 정렬을 1회전 할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.
  또한 1회전이 끝날 때마다 비교하는 정렬의 크기가 1씩 줄어드는 특징을 갖는다.
  즉 배열의 길이가 N이라면, N*(N+1)/2의 반복이 필요하고 이는 시간복잡도 O(N^2)을 가져 비효율적인 알고리즘이라 할 수 있다. 하지만 다른 정렬의 기본이 되는 개념이므로 꼭 알고 넘어가야 한다.

예시

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

생각

한번 수행할 때마다 반복횟수가 줄어들어야 하므로 이중 for문을 사용해야겠다. 1회전마다 j의 범위가 1씩 줄어들게 설정하고, 배열의 요소는 reference type임을 이용해여 임시변수를 활용해 배열의 요소를 옮겨줘야겠다.

풀이

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

깨달은 점

이중반복문에서 이미 실행한 i번째 요소를 건들이지 않아야하기 때문에 j의 범위가 arr.length-i-1 임을 이해했다.
그리고 temp라는 임시변수를 통해 값을 저장해두고, 바뀐 자리에 할당해주는 코드가 신기했고 다른 문제에서도 활용할 수 있도록 해야겠다.