[TIL] 버블정렬

mocha·2021년 3월 10일
1

TIL

목록 보기
2/10
post-thumbnail

버블정렬의 이해

  • 인접한 두개의 요소끼리 값을 비교하고, 대소관계에 따라 위치를 바꾼다.
  • 시간복잡도는 O(n2) 이며, 공간복잡도는 O(n)이다.

방법 1.

function get(str) {
  let arr = str.split(' ').map((n) => parseInt(n));
  let length = arr.length;
  
  // 0 이상 일 때
  while (length) {
    for (let i = 0; i < length; i++) {
      // 만약 앞에게 뒤의것 보다 크다면
      if (arr[i] > arr[i + 1]) {
        // 앞의 것 미리 저장해두고
        let temp = arr[i];
        // 뒤의 것은 앞에 걸로 변경하고
        arr[i] = arr[i + 1];
        // 앞의 것은 뒤의것으로 변경
        arr[i + 1] = temp;
        // 즉 앞 뒤 순서를 바꿈
      }
    }
    // while 구문 계속 하기 위해 --
    length--;
  }
  return arr;
}

console.log(get('4 2 3 8 5'));

방법 2

이론은 똑같음.
map을 두번 써서 for loop처럼 반복 시켜주는 것.
단지 이때는 위 처럼 temp변수를 안둬도 된다는 점이 장점이다.

function get(str) {
  let arr = str.split(' ').map((n) => parseInt(n, 10));
  
  arr.map((elem) =>
    arr.map((elem2, i) => {
      if (arr[i] > arr[i + 1]) {
        arr[i] = arr[i + 1];
        arr[i + 1] = elem2;
      }
    })
  );
  return arr;
}

console.log(get('4 2 3 8 5 7 41'));

👇 좀더 짧게 👇

function get(str) {
  let arr = str.split(' ').map((n) => parseInt(n, 10));
  arr.map((elem) =>
    arr.map((elem2, i) => {
      if (arr[i] > arr[i + 1]) {
        // destructuring 을 이용한 swapping!
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
      }
    })
  );
  return arr;
}
profile
고양이를 사랑하는 개발자😽

0개의 댓글