[JS] - Sorting Algorithm - Bubble Sort

📝 정렬 알고리즘에 대해서

• 정렬 (sorting) 은 데이터들을 특정 순서에 따라 재배치하는 프로세스를 의미
• 버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬 등이 있다

• 단순 (구현이 간단) 하지만 비효율적인 알고리즘
  📌 버블 정렬 (Bubble sort), 선택 정렬 (Selection sort), 삽입 정렬 (Insertion sort)

• 복잡하지만 효율적인 알고리즘
  📌 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬

버블 정렬 (Bubble Sort)

• 가장 큰 값이 버블처럼 위로 올라가는 모양을 하게 되는 알고리즘

• 서로 인접한 두 원소를 검사하여 정렬 하는 알고리즘

• 버블 정렬은 중복된 데이터가 있을 경우, 데이터의 위치를 교환하지 않고 지나가기 때문에 stable 한 정렬이다.

• 첫번째 자료와 두번째 자료를, 두번째 자료와 세번째 자료를, 세번째와 네번째 자료를 ... 이런식으로 마지막-1 번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬

• 1회전을 수행하고나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외, 2회전을 수행하고나면 끝에서 두번째 자료까지는 정렬에서 제외된다.

• n번째 정렬 회차가 끝나면 뒤에서 n번째 자리의 데이터가 확정

Big-O

• worst case : O(n^2) 정렬이 하나도 안되어 있는 경우
• best case : O(n) 이미 정렬이 되어있는 경우

버블 정렬의 경우 최악의 경우에 O(n^2) 의 시간 복잡도를 가진다.
왜냐면 각 자리를 찾기 위해 n번의 순회를 해야하고, n번의 회전 동안에 요소의 개수만큼 또 순회를 해야하기 때문이다.
그러나 이미 정렬이 되어있는 경우, 한번의 순회로 정렬 여부를 알 수 있다

버블 정렬의 장점

• in place 알고리즘으로, 메모리가 절약 된다는 장점이 있다
  👉🏻 in place 란 자료를 정렬할 때 추가적인 메모리 공간이 필요한 게 아닌, 데이터가 저장된 그 공간 내에서 정렬을 한다는 뜻

• 구현하기 쉬운 장점. 만약 이미 정렬이 되어있는 데이터를 순회하는 경우에는 n번만 순회하면 되기 때문에 정렬이 되었는지 안되었는지 테스트 용도로 사용될 수 있다

버블 정렬의 단점

• 버블 정렬의 가장 큰 단점은 자료의 개수가 많아질수록 성능이 매우 떨어진다
• 최악의 경우 시간 복잡도가 O(n^2) 까지 떨어지기 때문인데, 만약 데이터가 6개 뿐이라면 36번 순회를 해야하지만 데이터가 1000, 10000개 라면 .......

function bubbleSorting(arr) {
  for (let i = 0; i < arr.length; i++) {
    let swap;
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        swap = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = swap;
      }
    }
    console.log(`${i}회전: ${arr}`);
    if (!swap){
      break;
    }
  }
  return arr;
}

console.log(bubbleSorting([4, 2, 1, 5, 3]));

• i 가 0부터 arr.length 보다 작을 때까지 for 문을 돌린다
• 그 안에 j 가 arr.length - 1 -i 보다 작을 때까지 for 문을 돌린다
  👉🏻 arr.length - 1 - i 는 일단 arr[j] 와 arr[j+1] 을 비교하기 위해 사용
• 배열의 마지막 데이터를 포함하지 않아도 검색 대상에 포함되므로 마지막 1 을 빼주어야 한다
• 두번째로 각 회전 끝날 떄마다 마지막 데이터 정렬이 끝나기 때문에 i 를 빼주어야 한다
• swap 이라는 변수를 만들어,arr[j] 와 arr[j+1] 을 비교해서 arr[j]
  가 더 크면 자리를 교환
• 요소의 각 회전을 끝내고 swap 변수가 undefined 상태라면 "정렬이 다 되어있다" 라는 뜻이므로 for 문 종료