버블정렬

필요성

• 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]