버블정렬

송승찬·2020년 8월 31일
0

TIL

목록 보기
12/52

필요성

  • JS에는 Array.sort()함수가 존재한다.그러나
    정렬함수가 항상 좋은 퍼포먼스를 보장하지 않고 내가 가진 데이터의 양이나 상황에 따라 어떤 정렬을 사용하는 것이 좋을지 달라지기에 자주 쓰이는 몇 가지는 알아두려 한다.

버블정렬

  • 배열의 처음부터 시작

  • 인접한 두 원소의 크기를 비교,크기가 큰 쪽이 오른쪽에 가도록 하면서 계속 반복

  • 결국 1회 시행마다 가장 큰 원소가 배열의 가장 오른쪽 끝에 위치하게 된다

  • 매 시행마다 원소의 위치가 하나씩 결정되고,n번 시행시 뒤에서 n번째 원소의 위치가 결정된다

    장점

  • 구현이 쉬운 편

  • 메모리를 추가적으로 요구하지 않고(in place),데이터가 저장된 공간 내에서 정렬을 한다

    단점

  • 자료의 갯수가 많아질수록 많은 성능이 떨어짐

    Big O

    최악: O(n^2): 원소가 n개 있다고 했을때,정렬이 하나도 안되어 있는 경우 n번의 순회를 해야하며 n번의 회전 동안에 요소의 개수 n만큼 순회를 해야함
    최선: O(n): 이미 정렬이 되어있는 경우,한 번의 순회로 정렬 여부 확인 가능

let items = [18, 1, 9, 2, 5, 10, 15, 32, 88, 63, 18];

const bubbleSort = (array) => {
  let swap;
  
  //처음부터 마지막 원소 18까지 순회
  //매 시행마다 배열의 가장 오른쪽에 가장 큰 원소 위치
  //시행 횟수를 한 번씩 줄여줘야 함->i가 1씩 증가하는 만큼 줄여줌-> array.length-i해줌
  
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length - i-1; j++) {
      if (array[j] > array[j + 1]) {
        swap = array[j + 1];
        array[j + 1] = array[j];
        array[j] = swap;
      }
    }
  }
  return array;
};
console.log(bubbleSort(items));
//[1, 2, 5, 9, 10, 15, 18, 18, 32, 63, 88]
profile
superfly

0개의 댓글