알고리즘 문제풀이 toy - bubbleSort

 

문제 설명 : 정수를 요소를 갖는 배열을 입력받은 뒤 오름차순으로 정렬해서 리턴해야합니다.

단 arr.sort 사용은 하면 안됩니다. 입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다.

그리고 버블 정렬은 기본 정렬 알고리즘(삽입 정렬, 퀵 정렬,  병합 정렬, 기수 정렬) 중 1개입니다.  

 

 

 

입력
1 : arr

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

출력

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

 

 

입출력 예시

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

 

 

처음에 내가 접근했던 풀이 

반복문을 이용해서 수를 비교한 뒤 배열의 위치를 바꾸는 식으로 코드를 작성했으나 구현할 것도 많고 비효율적으로 보였다.

const bubbleSort2 = function (arr) {
  if (arr.length === 0) {
    return [];
  }
  //  console.log(arr.length);
  for (let j = 0; j < arr.length; j++) {
    for (let i = 0; i < arr.length; i++) {
      //   console.log("i", i);
      //   console.log(arr[i], arr[i + 1]);
      if (arr[i] > arr[i + 1]) {
        temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        //console.log("temp", temp);
      } else if (arr[i] === arr[arr.length - 2]) {
        if (arr[arr.length - 2] > arr[arr.length - 1]) {
          temp = arr[arr.length - 2];
          arr[i] = arr[arr.length - 1];
          arr[arr.length - 1] = temp;
        }
      }
      temp = "";
      //console.log("arr", arr);
    }
  }

  return arr;
};

 

두번째 코드는 배열 안에서 함수의 위치를 바꾸는 함수와  버블정렬 함수를 만들었고 여기서 핵심은 swap을 카운트해야한다는 생각과 j < N -i -1 이 개념을 이해하는 것이다. swap에 대해서는 기존에 swap을 했다면 그 대상은 swap에서 제외하는 것이고 그렇게 할 때마다 swap을 카운트한다. swap이 더 이상 증가하지 않으면 정렬이 완료된 것이기때문에 반복문의 탈출 조건으로 보면 된다. 

그리고 j < N -i -1에 대한 개념은 이미 정렬한 요소는 계산에서 빼기위한 것이다. 그렇게 한다면 알고리즘의 효율성이 올라간다.

다음은 2차 풀이 코드다.

 

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];
};



// 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'만 비교하면 된다.
    // N - 1 - i 번째는 이미 한번 정렬이 된 상태
    // 예를 들면 [5,4,3,2,1]에서
    // N - 1 - 0 = 4인데, 배열로 따지면 arr[4]이다.
    // 1회차 정렬을 실행하면
    // [4,3,2,1,5]이다. 따라서 arr[N -1 -i]는 arr[4]이고 밸류는 5이므로 5에 대해서는 정렬하지 않아도 된다. 이후 N 회차 정렬은 다음과 같다.
    // 2회차 정렬
    // [3,2,1,4,5]이다.  따라서 arr[N - 1 -i]는 arr[3]이다. 밸류는 4이므로 4에 대해서는 정렬하지 않아도 된다.
    // 3회차 정렬
    // [2,1,3,4,5]이다.  따라서 arr[N - 1 -i]는 arr[2]이다. 밸류는 3이므로 3에 대해서는 정렬하지 않아도 된다.
    // 4회차 정렬
    // [1,2,3,4,5]이다.  따라서 arr[N - 1 -i]는 arr[1]이다. 밸류는 2이므로 2에 대해서는 정렬하지 않아도 된다.

    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;
};

 

출처 : 코드스테이츠 참조