[JS] bubbleSort

입력

number 타입의 길이 1,000이하의 정수인 요소를 갖는 배열

출력

number 타입의 오름차순으로 정렬된 요소를 갖는 배열

주의사항

• arr.sort 사용은 금지된다.
• 버블 정렬로 구현해야 한다.
• parameter는 1차원 배열이다.

수도코드

버블정렬은 서로 인접한 두 요소를 검사하여 정렬하는 알고리즘이다.

arr를 인자로 받는 버블정렬함수 선언
const bubbleSort = function (arr) {};

결과값 변수에 빈배열 할당
let result = [];

인자 배열의 길이를 할당
let inputArrLength = arr.length;

n회전할 함수를 선언
let rotation = function (arr) {};

현재 요소와 다음요소를 비교하고
값이 작은 요소를 현재 요소에
값이 큰 요소를 다음 요소에 할당하는 반복문 구현

for(let i = 1; i < arr.length; i++){
  if(arr[i - 1] > arr[i]) {
    let pre = arr[i];
    let next = arr[i - 1];
    arr[i - 1] = pre;
    arr[i] = next;
  };
};

반복문이 끝나고 마지막 요소를 pop해 결과값 배열 앞에 unshift
result.unshift(arr.pop());

결과값 배열의 길이가 인자 배열의 길이가 될때까지 n회전 함수에 버블정렬함수 인자를 넣어 반복
while(result.length < inputArrLength){ arr = rotation(arr) };

결과값을 리턴
return result

코드

const bubbleSort = function (arr) {
  // TODO: 여기에 코드를 작성합니다.
  let result = [];
  let inputArrLength = arr.length;
  let rotation = function (arr) {
    for(let i = 1; i < arr.length; i++){
      if(arr[i - 1] > arr[i]) {
        let pre = arr[i];
        let next = arr[i - 1];
        arr[i - 1] = pre;
        arr[i] = next;
      } else {
        continue;
      }
    }
    let last = arr.pop();
    result.unshift(last);
    return arr;
  }

  while(result.length < inputArrLength){
    arr = rotation(arr);
  }
  return result;
};

버블정렬의 구현방식을 보고 함수를 작성해본 결과 의도한대로 작동은 하였지만
최대 길이가 80,000인 정수 배열을 넣을 경우 수행시간이 2000ms가 넘어갔다.

더 나은 코드

let bubbleSort = function (arr) {
  let N = arr.length;
  for (let i = 0; i < N; i++) {
    let swaps = 0;
    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;
};

swap된 횟수를 기록해 이미 정렬된 요소를 계산하지 않아 수행시간을 줄였다.