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

bubbleSort

문제

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다. 버블 정렬(bubble sort)은 여러 정렬 알고리즘(삽입 정렬, 퀵 정렬, 병합 정렬, 기수 정렬 등) 중 가장 기본적인 알고리즘입니다.

버블 정렬 알고리즘은 아래와 같습니다.

1. 첫 번째 요소가 두 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap)
2. 두 번째 요소와 세 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap)
3. 1, 2를 마지막까지 반복합니다. (마지막에서 두 번째 요소와 마지막 요소를 비교)
4. 1~3의 과정을 한 번 거치게 되면, 가장 큰 요소가 배열의 마지막으로 밀려납니다.
5. 1~3의 과정을 첫 요소부터 다시 반복합니다.
6. 5를 통해 두 번째로 큰 요소가 배열의 마지막 바로 두 번째로 밀려납니다.
7. 1~3의 과정을 총 n번(배열의 크기) 반복합니다.

이 모습이 마치 '거품이 밀려 올라가는 것과 같은 모습'과 같아서 bubble sort라고 부릅니다.

입력

인자 1 : arr

• number 타입을 요소로 갖는 배열
• arr[i]는 정수
• arr[i]의 길이는 1,000 이하

출력

• number 타입을 요소로 갖는 배열을 리턴해야 합니다.
• 배열의 요소는 오름차순으로 정렬되어야 합니다.
• arr[i] <= arr[j] (i < j)

주의사항

• 위에서 설명한 알고리즘을 구현해야 합니다.
• arr.sort 사용은 금지됩니다.
• 입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다.

입출력 예시

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

Advanced

• 아래의 힌트를 바탕으로 (최선의 경우) 수행 시간을 단축할 수 있도록 코드를 수정해보세요.
• 위에서 설명된 알고리즘 1~3의 과정 중 어떤 요소도 위치가 바뀌지 않은 경우, 배열이 정렬된 상태라는 것을 알 수 있습니다.

문제풀이

거품정렬이 어떻게 작동하는지 먼저 찾아봤다.

거품 정렬(Bubble Sort) | 👨🏻‍💻 Tech Interview

버블정렬은  두 인접한 원소를 검사하여 정렬하는 방법이고 시간복잡도가 O(n2) 으로 상당히 느린편에 속하지만, 코드가 단순해서 자주 사용된다고 한다

과정을 먼저 살펴보면

1. 앞에서부터 다음 인덱스와 비교한다.(인접한 인덱스끼리 비교)
2. 큰 것은 뒤로 보낸다.
3. 배열의 끝까지 1~2과정을 반복하며, 한 회전이 끝나면  다시 앞으로 돌아와 1~2의 과정을 반복한다.

예를 들어, 다음과 같은 배열을 생각해볼 때,

[3, 5, 1, 2, 4]

1. [3, 5, 1, 2, 4]에서 3과 5 비교, 그대로 유지
2. [3, 5, 1, 2, 4]에서 5와 1 비교, 1이 작으므로 자리 교환 -> [3, 1, 5, 2, 4]
3. [3, 1, 5, 2, 4]에서 5와 2 비교, 2가 작으므로 자리 교환 -> [3, 1, 2, 5, 4]
4. [3, 1, 2, 5, 4]에서 5와 4 비교, 4가 작으므로 자리 교환 -> [3, 1, 2, 4, 5]

이제 다시 처음으로 돌아가서 1~4번 과정을 첫번째 인덱스부터 다시 반복한다. 앞에서 했던 반복을 배열의 크기 - 1번 만큼 진행하면 정렬이 완료된다.

즉, 한 회전이 끝나면 다시 처음으로 ( 첫번째 인덱스로 ) 돌아가 위 과정을 반복해주고 최종적으로 오름차순으로 정렬된다.

const bubbleSort = function (arr) {
    const len = arr.length;
      for (let i = 0; i < len - 1; i++) {
        for (let j = 0; j < len - i - 1; j++) {
          if (arr[j] > arr[j + 1]) {
            // 인접한 두 요소를 비교하고, 앞쪽 값이 더 크면 위치를 바꾸기
            const temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
          }
        }
      }
      return arr;
};

위의 코드로 작성하게되면 'bubbleSort Advanced 최대 길이 80,000의 자연수 배열을 정렬해야 합니다' 의 마지막 문제 오류가 뜬다.

시간복잡도를 생각해서 다시 풀라는 말이라 기존의 반복했던것 중 배열의 순서가 제대로 되어있다면 기억해두고 반복작업을 하지 않도록 했다.

const bubbleSort = function (arr) {
    const len = arr.length;
      let isSorted = true;

      for (let i = 0; i < len - 1; i++) {
        for (let j = 0; j < len - i - 1; j++) {
          if (arr[j] > arr[j + 1]) {
            const temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
            isSorted = false;
          }
        }

        if (isSorted) {
          // 정렬이 완료된 경우
          return arr;
        }

        // 다음 반복을 위해 초기화
        isSorted = true;
      }

      return arr;
  };

기억해둔 배열이 이미 정렬된 경우, 불필요한 연산을 줄이기 위해 추가적인 작업이 필요하고. 이를 위해서는 정렬 작업 도중에 인접한 두 요소의 자리 교환 작업을 하지 않고, 모든 요소를 한 번만 순회하면서 정렬 여부를 확인하는 작업이 필요했다.

변경된 코드에서는 먼저 isSorted라는 변수를 추가하고, 초기값을 true로 설정하고. 정렬 작업을 수행하는 반복문 내부에서는 자리 교환 작업을 수행할 때마다 isSorted 값을 false로 변경한다. 그리고 내부 반복문이 완료된 후 isSorted 값이 여전히 true인 경우는 모든 요소가 정렬되어 있으므로, 배열을 반환한다. 정렬이 완료된 이후에도 계속해서 반복문을 수행하지 않도록 하기 위해 isSorted 값을 다시 true로 초기화시킨다.

레퍼런스 코드

const swap = function (idx1, idx2, arr) {
  // 두 변수를 바꾸는 방법

  // 1) 임시 변수를 활용한 방법
  // let temp = arr[idx1];
  // arr[idx1] = arr[idx2];
  // arr[idx2] = temp;

  // 2) Destructuring assignment를 활용한 방법
  // arr이 reference type이라 가능
  [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];

  // 3) XOR 연산을 활용한 방법
  // arr이 reference type이라 가능
  // arr[idx1] ^= arr[idx2];
  // arr[idx2] ^= arr[idx1];
  // arr[idx1] ^= arr[idx2];
};

// naive solution
// let bubbleSort = function (arr) {
//   let N = arr.length;

//   for (let i = 0; i < N - 1; i++) {
//     // 매 반복(iteration)마다 i번째로 큰 수가 마지막에서 i번째 위치하게 된다.
//     // 이미 정렬된 요소는 고려할 필요가 없으므로, 'j < N - 1 - i'만 비교하면 된다.
//     for (let j = 0; j < N - 1 - i; j++) {
//       if (arr[j] > arr[j + 1]) {
//         swap(j, j + 1, arr);
//       }
//     }
//   }

//   return arr;
// };

// optimized solution
let bubbleSort = function (arr) {
  let N = arr.length;

  for (let i = 0; i < N; i++) {
    // swap 횟수를 기록한다.
    // 어떤 요소도 swap되지 않은 경우, 배열은 정렬된 상태이다.
    let swaps = 0;

    // 매 반복(iteration)마다 i번째로 큰 수가 마지막에서 i번째 위치하게 된다.
    // 이미 정렬된 요소는 고려할 필요가 없으므로, 'j < N - 1 - i'만 비교하면 된다.
    for (let j = 0; j < N - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        swaps++;
        swap(j, j + 1, arr);
      }
    }

    if (swaps === 0) {
      break;
    }
  }

  return arr;
};