알고리즘 면접 질문) "sort와 search의 관계를 설명해주세요"

관계 1. sort 는 search 전 할 수 있는 전처리 과정이다.

 

다음 기준으로 sort가 필요한지 아닌지 알 수 있다:

> data에 대한 search가 1회성이다. -> linear search 사용.

>> linear search의 검색 시간은 O(n) 이다.

 

> data에 대한 search가 반복적이다. -> sort 후 binary search 사용

>> binary search의 검색 시간은 O(log n) 이다.

 

그런데 sort에 드는 시간은 얼마일까?

> 

 

관계 2. 

---

부록 1. sort 알고리즘 종류와 선택 기준

 

종류:

• O(n^2) 알고리즘: bubble, selection, insertion
  • bubble: 왼쪽, 오른쪽 비교해서 왼쪽이 더 크면 오른쪽과 교체. 한 pass가 지나면 끝에 가장 큰 값이 남음
  • selection: 가장 큰 값의 인덱스를 찾음. 가장 큰 값과 마지막 자리의 값과 교체. 가장 큰 값이 마지막 자리에 있게 됨
  • insertion: 자신의 왼쪽보다 자신이 작다? 그러면 정렬되지 않은 것으로 판단. 맨 왼쪽부터 비교해 자신의 자리를 찾아간다. 정렬되지 않은 경우 최대 (n-1) 만큼 비교가 필요함.
• O(n * log n) 알고리즘: quick, merge, heap
  • quick: 
    • 분할 단계:
      • 시간 복잡도:
        • 평균: O(n * log n)
          • n: 분할 당 pivot과 비교를 n-1 번 해서 자리를 찾아야함
          • log n: pivot을 잘 선택하였다는 가정하에 평균 log n 번 분할 해야 함
        • 최악: O(n * n)
          • n: 분할 당 pivot과 비교를 n-1 번 해서 자리를 찾아야함
          • n: pivot이 항상 최대값 또는 최소값으로 선택되어 재귀적으로 n-1 번 해야 정렬 완료됨
  • merge:
    • 나눔 단계:
      • 시간 복잡도: O(log n). log₂N 이란 값은 2를 몇번 곱해야 N이 나올 때 몇번에 해당하는 값이다. 우리는 2로 나누는 일을 하고 있으므로, 이를 N을 2로 나눠서 결국 N이 1이 될 때 까지 몇번 나눠야 하는가로 이해해야 된다.
        • log₂8: 2를 3번 곱해야 8이 된다. 3은 2로 곱하는 작업을 3번 해야된다는 뜻이다. 또는, 8을 2로 나눠서 1일 되기 까지 나누는 작업을 3번 해야 된다는 뜻이다.  
    • 병합 단계:
      • 두 개의 리스트를 비교하면서 최종 리스트 생성
        • 시간 복잡도: O(n)
          • 최대 최종 리스트 원소 갯수 만큼 비교 필요
      • 최종 리스트를 생성하는 행위를 log₂N 만큼 해야함
        • 시간 복잡도: O(log n)
      • 총 시간 복잡도: O(n * log n)
    • 총 시간 복잡도: O(n) + O(n log n) = O(n log n)
      • 최악의 시간 복잡도는 더 큰 차수의 항을 취함
  • heap sort:
    • 빌드 heap 단계:
      • heapify-down:
        •  array를 binary tree로 표현한다
        • 대상은 맨 밑에를 제외한 자식이 있는 부모부터
        • 맨 밑 레벨부터 왼쪽부터 노드 하나씩 heapify 진행한다.
        • heapify 로직에 의해 부모와 자식이 바뀌면, 바뀐 자식을 부모로 다시 부모-자식 관계를 검사한다.
        • 가장 끝에는 루트 노드의 heapify 진행한다.
          • 루트 노드의 heapify는 가장 비용이 크다.
      • 시간 복잡도: O(n)
        • 루트 노드는 레벨 0
        • 레벨 k 가 주어졌을 때, 레벨 별 시간 복잡도: 노드 개수 * heapify 비용
          • 노드 갯수: 2^k
          • heapify 비용: log₂n - k
          • 레벨 별 시간 복잡도: 2^k * (log₂n - k)
        • 레벨은 0부터 log₂n 까지 존재함
          • Σ from 0 to log₂n
        • 총 시간 복잡도: O(n)
          • 레벨 1 시간 복잡도 + 레벨 2 시간 복잡도 + ... = Σ 2^k(log₂n - k) = Σ 2^k
            • k가 늘어나면서 2^k가 커지는 것이 -k 를 압도함
          • Σ from 0 to log₂n of 2^k 는 등비수열 공식에 의해 2n-1 과 같음
            • 빅오 표기법에 의해 2n-1은 O(n) 으로 표현됨
    • sort 단계:
      • 방법: max-heap이 생겼으면 max 값을 뺀다. 나머지로 다시 max-heap을 만든다.
      • 시간 복잡도: O(n log n)
        • log n: root node에 대해서 heapify 를 진행하므로, root node heapify 1회 비용
        • n log n: n개의 root node에 대해서 heapify 진행
    • 총 시간복잡도: O(n) + O(n log n) = O(n log n)
      • 가장 큰 항의 시간 복잡도만 가져감

heap sort와 quick sort 비교:

• merge sort는 build heap 비용으로 인해 더 느리다

quick sort와 merge sort 비교:

• quick sort는 in-place sorting의 locality of reference로 인해 cache 사용면에서 좋다
  • 하나의 배열 내 연속적인 데이터를 접근한다
• merge sort는 병합 시 새로운 리스트를 만들 필요가 있어서 추가 메모리 공간이 필요하다
  • 즉, 메모리 복사 비용이 발생한다
• quick sort는 unstable sort이다.. 기존 array가 갖는 순서를 유지하지 않는다.
  • 예시로, 기존 array가 이름 순으로 이미 정렬이 된 상황에서, 추가적으로 성적순으로 정렬하고자 할 때는 stable sort를 써야 한다.
  • 알고리즘 특성상 병합 시 merge sort는 왼쪽에 먼저 온다면 왼쪽에 먼저 배정됨. 왼쪽부터 검사함.
  • 알고리즘 특성상 병합 시 quick sort는 pivot을 기준으로 자리를 바꾸면 왼쪽에 있는 것이 오히려 더 오른쪽에 위치하게됨 (미리 자리를 바꿈으로)
• quick sort의 최악은 O(n^2) 이다. merge sort는 O(n log n) 이다.

부록 2. C++의 std::sort 의 알고리즘

 

IntroSort:

• 퀵정렬과 삽입정렬의 조합
• 퀵정렬의 단점: 재귀가 깊어 질 수 있음
  • 재귀가 너무 깊어지면 힙정렬이나 병합정렬로 전환

그 외. timsort:

• python의 sorted 나 java의 Arrays.sort 에서 사용
• 삽입 정렬과 병합 정렬의 조합
• 데이터를 run으로 나눔
  • 각 run은 삽입 정렬로 sort
  • sort된 run을 합칠 때 병합 정렬로 합침
• 시간 복잡도:
  
  • 최선: insertion sort의 O(n)