[4장] 빅 오로 코드 속도 올리기

'정렬되지 않은 배열을 어떻게 오름차순으로 정렬할 수 있을까?'

정렬 알고리즘은 생각보다 폭넓게 연구된 주제이며, 
지난 수년간 수십 개의 정렬 알고리즘이 개발돼 왔다.

그 중 단순 정렬(simple sort)에 속하는 버블정렬에 대해 알아보자
물론 효율적인 정렬은 아님

4.1 버블 정렬(단순 정렬, simple sort)
이웃한 두 원소의 대소 관계 비교 및 교환을 계속 해나가는 정렬.

교환이 일어나지 않는게 확인될 때까지 계속해서 검색을 지속한다.

 

여기서 '버블'이란 정렬되지 않은 값 중 가장 큰 값을 말하는데

각 패스스루마다 버블이 올바른 위치로 가게 되므로 '버블정렬' 이라고 부른다.

아무튼 매우 쓰레기같은 비효율적인 정렬

 

4.2 버블 정렬 실제로 해보기
[ 4, 2, 7, 1, 3 ] 을 정렬해보자

 

너무 귀찮아서 못하겠는데 총 16단계에 3패스스루를 시행하게된다.

4.2.1 버블 정렬 구현

function bubbleSort(arr: any[]) {
  const copy = arr;

  for (let i=0; i<arr.length; i++) {
    for (let j=i+1; j<arr.length; j++) {
      if (arr[j] < arr[i]) {
        [ copy[i], copy[j] ] = [ copy[j], copy[i] ];
      }
    }
  }
  return copy;
}

4.3 버블 정렬 효율성 ; O(N2)
버블 정렬 알고리즘은 두 가지 단계를 거치는데
  - 비교(comparison) : 어느 쪽이 더 큰지 비교
  - 교환(swap) : 두 수를 교환

원소가 N개이고, 최악의 시나리오에선 모든 패스스루에서 비교 및 교환이 때마다 일어날테니
(물론 매 패스스루마다 마지막 값은 제대로 정렬이 되므로 확인할 필요는 없어지겠지만)
  - 비교 : (N-1) + (N-2) + (N-3) + ... + 1 
  - 교환 : (N-1) + (N-2) + (N-3) + ... + 1 
    ☞ N(N-1) 스탭을 거치게 된다

즉, 근사적으로 버블 정렬의 효율성은 O(N²) ← 이차 시간(quadratic time) 이라고 부른다
회생 불가능한 쓰레기다

4.4 이차 문제
통상 O(N²) 알고리즘은 중첩 루프를 사용하는 경우에 많이들 발생하곤 한다.
예를 들어, [1, 3, 5, 7, 9, 1 ] 에서 중복 값이 있는지 확인하는 경우

function isDupulicated( array ) {
    for (let i=0; i < array.length; i++) {
        for (let j=0; j < array.length; j++) {
            if ( i !== j && array[i] === array[j] ) {
                return true;
            }
        }
    }
    return false;
}

앞으론 O(N²) 알고리즘이다 생각이 들면
내가 짠 코드는 회생 불가능한 쓰레기다 라는 생각이 들어야한다

4.5 선형 해결법
중첩루프를 쓰지 않는 방식으로 위 함수를 바꿔보자

function isDuplicated2( array ) {
    const searchArray = [ ];
    for (let i=0; i < array.length; i++) {
        if ( searchArray[ array[i] ] === 1 ) {
            return true;
        } else {
            searchArray[ array[i] ] = 1;
        }    
}

무슨 함수인지 알겠는가? 루프를 돌리면 아래와 같은 모양새가 나온다

searchArray = [ 
    undefined,      1      , undefined, 
    undefined, undefined,       1     , 
    undefined,      1      , undefined, 
    1
];

즉 [1, 3, 5, 7, 9, 1] 각 값에 맞는 자리를 1로 채우고
만약 중복되는 값이 나오면 '이미 그 자리엔 1이 있다 닝겐' 
하면서 중복된다고 내뿜는 알고리즘이다. 
심지어 O(N)으로 훨씬 효율적