Udemy - 버블 정렬

---

정렬 알고리즘에는 정말 많은 종류가 존재한다.
하지만 모두 상황에 따라 사용해야 하며, 어떤 상황에서나 완벽하게 적용되는 단 하나의 정렬 알고리즘은 존재하지 않는다.
따라서 오늘은 가장 일반적인 버블정렬 알고리즘에 대해 정리해보고자 한다.

---

정렬을 왜 배워야 하는가?

프로그래밍 또는 알고리즘에서 정말 자주 사용되는 알고리즘이기 때문이다.

1. 삽입, 선택, 버블, 쉘, 병합, 힙, 퀵 정렬 등의 다양한 정렬 알고리즘들이 존재한다.

   💡 가장 기초적인 정렬 알고리즘은 버블, 선택, 삽입 정렬 알고리즘이다. (효율성도 조금 떨어짐)
   => 그래도 특정 상황에서는 매우 효율적일 수 있음

2. 상황에 따라 효율적인 정렬 알고리즘이 있다. (장단점들이 각기 존재함)

3. 면접에 빈출되는 주제다.

---

sort 자바스크립트 내장함수

평소에 자주 사용했던 sort() 자바스크립트 내장 함수다.
시간복잡도는 기본적으로 O(N)이지만 MDN에 따르면 인풋의 크기에 따라 복잡도가 달라질 수 있다고 한다.

sort()내장함수는 때에 따라서는 굉장히 손쉽게 사용할 수 있지만, 모든 정렬 기준이 배열 내의 값들을 유니코드(String)으로 변환한 후 → 해당 값을 기준으로 정렬을 한다. 따라서 내가 원하는 결과값을 얻지 못할 확률이 높다.

이를 방지하기 위해 comparator함수를 활용할 수 있다.

// 오름차순 정렬
somethig.sort((a, b) => a - b);

// 내림차순 정렬
something.sort((a, b) => b - a);

---

버블 정렬

자주 사용되지는 않는 정렬 알고리즘이다.
그래도 이 정렬 알고리즘을 배워야 하는 이유는, 다른 알고리즘들이 얼마나 효율적인지 역체감을 할 수 있기 때문이다.

물론 이와 같이 배열의 순서를 반복문 안에서 계속 변경해줘야 한다는 점과, 지속적인 순회를 해야된다는 점이 까다롭다. 하지만 매 반복마다 순회해야 하는 배열의 길이가 짧아진다는 점도 잊어서는 안된다.

1. 위치 바꾸기

   

   위와 같이 ES6 문법을 사용해서 쉽게 두 요소의 위치를 바꿔줄 수 있다.

2. 기본 예제

   배열 요소들을 오름차순으로 정렬하는 버블 정렬 알고리즘을 작성하시오.
   j와 i 포인터 활용

   function bubble(arr) {
     let i = arr.length - 1;
     let j = 0;
     while (i > 0) {
       if (j === i) {
         j = 0;
         i--;
       }
       if (arr[j] > arr[j + 1]) {
         [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
       }
       j++;
     }
     return arr;
   }
   
   bubble([29, 10, 14, 37, 14]);

3. 버블정렬 최적화

   버블정렬의 특성상, 매우 긴 배열에서 이미 정렬이 끝났음에도 불구하고 계속 i가 1에 닿을 때 까지 반복문을 돌린다. 이는 굉장히 비효율적이므로 최적화를 통해 이러한 문제점을 해결해야 한다.

   

   function bubble(arr) {
     let i = arr.length - 1;
     let j = 0;
     // isSwap이라는 변수를 활용한다.
     let isSwap;
     while (i > 0) {
       // j가 끝에 닿아서 다시 0부터 탐색을 해야 할 때 isSwap을 체크한다.
       if (j === i) {
         if (!isSwap) break;
         // isSwap, 즉 위치 변경이 일어났다면 다시 isSwap을 false로 초기화 시킨다.
         isSwap = false;
         j = 0;
         i--;
       }
       // 만약 j가 i에 닿을때 까지 정렬이 한번도 안일어나면 초기의 isSwap=false 값이 유지될 것이다.
       // 이에 따라 반복문은 break 된다.
       if (arr[j] > arr[j + 1]) {
         [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
         isSwap = true;
       }
       j++;
     }
     return arr;
   }

---

버블정렬의 시간복잡도

1. 정렬이 이미 많이 된 배열에 대해서는 O(N)의 시간복잡도를 가질 수 있다.

   (위에서 활용한 isSwap을 사용)

2. 하지만 일반적인 경우의 버블정렬 시간복잡도는 O($$n^2$$)이다.

---