[Udemy 알고리즘&자료구조] 정렬(버블정렬)

1. 왜 정렬을 배워야 하는가?

    a. 정렬은 프로그래밍에서 매우 자주 쓰인다. 또한 많은 면접관련 책들은 정렬에 많은 시간을 할애할 만큼 중요하다.
    b. 같은 결과를 도출하는 수 많은 알고리즘이 있고, 각각 장단점이 있다. 상황에 따라 더 적합한 알고리즘이 존재한다.

2. 기본적으로 내장된 자바스크립트 정렬

    a. array.sort
        i. callback함수를 이용하여, 정렬방식을 정할 수 있다. 인자는 a 와 b 두개.
        ii. a-b값에 대해 함수가 음수를 반환하면 a가 b앞에 오는 것으로 결정한다. 양수면 반대로. (오름차순)
        iii. b - a로 설정하면, 내림차순이 된다.

3. 버블정렬

    a. 개념 : 오른차순으로 정렬할 때 더 큰 숫자가 한 번에 하나씩 뒤로 이동한다.
    b. 효율적인 정렬은 아니다. 그래서 많이 사용하지도 않고, 많이 배우지도 않는다.
    c. 하지만 두각을 나타내는 분야가 있는데 나중에 나온다.
    d. 작동방식
        i. 배열의 첫번째부터 그 다음 숫자와 비교를 하면서 앞에 숫자가 뒤에 숫자보다 크면 자리를 교환한다. 이걸 끝까지 반복했다가, 다시 처음으로 돌아와서 첫번째 숫자부터 그 다음에 위치한 숫자와 비교를 한다. 이걸 반복하는 것임.

4. 버블정렬 구현

/* 버블정렬 구현:
1. 첫번째 루프(i)는 뒤에서 앞으로. 무의미한 비교를 줄여준다. i가 앞에서부터 시작한다면, j는 i-1까지 가는 것이 아니라 array.length까지 가야하는데, 그러면 i가 증가될 때마다 j는 array.length까지 가기때문에 이미 정렬된 요소들에 대한 비교를 실행할 수밖에 없다.
2. 내부루프(j) : 앞에서 i-1까지
3. j는 j+1과 비교한다. 그리고 arr[j]가 arr[j+1]보다 크면 교환한다. */
//교환식
function swap(array, index1, index2) {
  let temporary = array[index1];
  array[index1] = array[index2];
  array[index2] = temporary;
  /* ES2015버전
  [arr[index1],arr[index2]] = [arr[index2],arr[index1]] */

}
function bubbleSort(array) {
  for (let i = array.length; i >= 0; i--) {
    for (let j = 0; j < i - 1; j++) {
      if (array[j] > array[j + 1]) {
        swap(array, j, j + 1);
      }
    }
  }
  return array;
}
const testArr = [
  4, 55, 46, 42, 1, 23, 23, 45, 356, 457, 76, 867585, 7, 3456, 234, 234, 231,
  23, 12, 3,
];
const testFunc = bubbleSort(testArr);
console.log(testFunc);

시키는 대로 해봤는데 찰떡같이 된다.

5. 버블정렬 최적화

a. 문제점 : 지금 상태에서는 정렬이 거의 다된, 일부분만 정렬이 안된 배열에 대해서도 버블정렬은 끝에서부터 배열의 첫 번째자리까지 모두 정렬을 할 것이다. 정렬이 완료된 후라 하더라도 말이다.
b. 해결방법 : 그래서 이번 루프에서 값을 교환한 것이 있는지 여부를 확인한 후에 교환한 요소가 없다면 정렬을 끝내는 것이 버블정렬을 최적화하는 방법이다.
c. 20자리의 배열 중 숫자 2개만 정렬이 안됐다고 가정했을 때, 최적화를 한 함수는 54번 연산을 했고, 최적화를 하지 않은 함수는 190번 연산을 했다.

    function bubbleSort(array) {
      let count = 0;
      for (let i = array.length; i >= 0; i--) {
        let isSwap = false;
        for (let j = 0; j < i - 1; j++) {
          if (array[j] > array[j + 1]) {
            swap(array, j, j + 1);
            isSwap = true;
          }
          count++;
        }
        if (!isSwap) break;
      }
      return array;
    }

이렇게 isSwap이라는 변수를 이용해 swap을 했는지 확인한다. 그리고 j반복문이 끝나면, 다시 isSwap을 false로 바꿔주는데 만약 j반복문에 swap을 안했다면, 반복문은 break로 인해 종료된다.

6. 버블정렬의 시간복잡도

    a. 일반적으로는 O(n^2)이다.

하지만, 정렬이 거의 다 된 상태이고 최적화를 했다면 O(n)에 가깝다. (최상의 상태일 때)