[알고리즘] 비교 기반 정렬 문제

정렬 문제→ 여러 방법이 존재하며, 방법마다 특징이 다름

• → 시간복잡도, 최적성에 대해 증명이 쉬움
• → n개의 서로 다른 수가 주어질 떄, 이들을 이동하여 점점 커지게(오름차순) 또는 점점 작아지게(내림차순)으로 만드는 문제

가정 : 정렬한 데이터가 담긴 배열의 각 원소를 O(1)시간에 접근 가능하다. (= 데이터가 메인 메모리에 저장되어 있다.)

버블 정렬

맨 왼쪽 원소부터 바로 이웃한 원소와 비교해가면서, 큰 수가 오른쪽으로 가도록 교환함.

맨 끝까지 가면 가장 큰 원소를 찾은 것이므로, 이 과정을 다시 나머지 n-1개 수에 대해서 반복

• 정확성 : 자명함
• 시간 복잡도 : 처음 가장 큰 원소를 구할 때 n-1번 비교, 두 번째 큰 원소를 구할 때 n-2번 비교
  • (n-1) + (n-2) + … + 1 = n(n-1)/2 = Θ(n^2)
  • 입력 순서와 무관하게 n개의 값을 정렬할 때 항상 똑같은 횟수의 비교를 수행함

삽입 정렬

정렬 대상이 될 원소를 두 부분으로 나눔

• 앞은 “이미 정렬된 부분” (오름차순 만족)
• 뒤는 “정렬할 부분”
• 매번 정렬할 부분의 가장 첫번쨰 원소를 정렬된 부분에 삽입(insertion)
• 삽입은 정렬된 부분의 가장 큰 원소(가장 오른쪽 원소)부터 왼쪽으로 비교해나가면서 진행.
• 정확성 :
  • 이미 정렬된 부분은 항상 정렬되어있음.
  • 매번 정렬할 부분의 원소 1개를 정렬된 부분으로 옮긴다.
  • 정렬할 부분의 원소는 처음에 n-1개, 매번 1개씩 감소하므로 최종적으로는 정렬된 부분 n개, 정렬할 부분에 0개
  • 정렬된 부분은 정렬이 되어있으므로 정확

ex)

• 시간 복잡도 :
  • Best = 이미 오름차순으로 정렬되어 있을 때, 정렬된 부분에 원소를 넣을 때 마다 비교를 한번씩만 하면 됨
    • 총 n-1번 = Θ(n)
  • Worst = 역순으로 정렬된 수를 정렬할 때
    • i번째 위치의 원소를 정렬된 부분에 추가할 때, 앞부분의 i-1개 원소들과 모두 비교해야함
    • i = 2,3, … ,n 이므로, 1+2+ … + n-1 = n(n-1)/2 = Θ(n^2)
• 평균 시간복잡도 = i개의 정렬된 부분에 i+1번째 원소를 삽입할 때
  • 삽입 후 : 정렬된 부분 i+1개, 새로 들어온 원소는 1등 ~ i+1등 중 하나.
  • i+1등할 확률 = 1/(i+1), 비교 1번
  • i등할 확률 = 1/(i+1), 비교 2번
  …
  • 3등 확률 = 1/(i+1), 비교 i-1번
  • 2등 확률 = 1/(i+1), 비교 i번
  • 1등 확률 = 1/(i+1), 비교 i번 (맨앞 원소와 비교 후 1등vs2등 결정하므로)
  i+1번째 원소를 추가할 때 평균 비교횟수는, [ 1/(i+1) * {1+2+ … + i-1 + i} ] + 1/(i+1)*i

O(n^2)보다 빠르게 정렬할 수 있는가?

• 인접한 두 원소를 교환하는 방식의 정렬 알고리즘은 O(n^2)보다 빨리 정렬할 수 없다. (O(n^2)가 최적이다!)
• 증명 : n개의 서로 다른 값을 가지는 원소를 나열하는 방법은 n! 가지이지만, 정렬된 결과는 단 한가지이다.
  • n개의 원소 중 2개를 뽑는 방법은 (n,2)가지
  • 정렬되지 않았다면, 순서가 틀린 쌍이 존재한다. 정렬되었다면, 순서가 틀린 쌍이 없다.
  • 인접한 두 원소를 교환하면 틀린 쌍 중 오로지 한 쌍이 제거된다.
  • 최악의 경우, 모든 쌍의 순서가 잘못되어 있다.
  • 따라서 (n,2) = O(n^2)번의 교환이 필요하다.

 

 

분할 정복 기법 (Divide and Conquer)

착안점 : 문제의 크기가 커질수록 더 풀기 어렵다.

• Divide = 원래 문제를 독립적으로 풀 수 있는 작은 문제로 나눈다.
• Delegate = 각각의 작은 문제를 푼다.
• Combine = 각 문제의 답을 이용하여 원래 문제의 답을 만든다.

정렬 문제에 대한 분할정복 기법 : 병합 정렬 (Merge sort) & 퀵 정렬 (Quick sort)

 

병합 정렬

• Divide = 정렬할 리스트를 앞쪽 반/뒤쪽 반으로 나눈다.
• Delegate = 앞쪽 반을 정렬
• Delegate(2) = 뒤쪽 반을 정렬
• Combine = 둘을 합쳐서 하나의 정렬 리스트를 만든다.

➢ 앞쪽 반, 뒤쪽 반은 병합 정렬로 재귀적으로 정렬한다.

➢ 리스트의 길이가 1이면 그 자체가 정렬되어 있다. 또는, 어느정도 길이 이하이면 다른방법으로 정렬할 수도 있다.

➢ 둘을 합쳐서 하나의 정렬된 리스트는?

오름차순으로 정렬된 두 리스트 A, B의 병합 → 맨 처음 원소를 비교하여 작은 쪽을 새로운 리스트에 삽입.

→ 이 삽입된 원소를 제거하고 재귀적으로 진행.

• 정확성 : A, B 중 하나가 비어있는 경우 → 나머지 하나는 이미 정렬된 상태이므로 병합 결과는 그 자신이다. 정렬&정확
  • 귀납 단계 - A, B 둘다 비어있지 않다면? → 리스트에 들어가는 원소는 모든 원소 중 최소값.
  • 재귀적으로 진행되는 과정에서, A, B 중 하나는 원래보다 원소가 하나 적다.
• 알고리즘의 진행
  1. 전체 리스트의 앞쪽 반, 뒤쪽 반을 병합정렬로 정렬
  2. 병합 정렬에 의해 앞쪽 반, 뒤쪽 반 모두 정렬 완료
  3. 두 리스트를 병합

• 두 리스트 병합의 시간 복잡도 : Best = 교차되는 부분이 없을 때 n/2
  • 실제 정렬 : 정렬된 리스트를 연속으로 병합, 최종 단계에서는 정렬 완료 상태
  • 점화식 : T(n) = 2T(n/2) + n, T(n) = Θ(n log n)
    • n/2개의 리스트 2개를 정렬하고, 합칠 때 n번 비교함.
  • 입력 형태에 상관없이 항상 같은 시간복잡도 보장, 항상 문제의 크기가 1/2로 줄어듬
  • 실제로는 원소들이 더 자주 움직여서 시간이 더 많이 걸림.
  • 퀵 정렬의 경우, 일단 순서가 정해진 원소는 움직이지 않는다!
• Worst = 서로 모두 교차할 때 n
• 공간 복잡도 : A, B를 복사하는 경우 2n
• linked list로 구현하는 경우 n (A, B의 원래 내용은 파괴됨)

 

퀵 정렬

특정 원소를 중심으로 작은 것은 왼쪽, 큰 것은 오른쪽으로 & 재귀적 실행

왼쪽/오른쪽의 순서와 무관하게, 기준 원소의 순서는 결정된다.

ex)

• 시간 복잡도 :
  • Best = 기준의 왼쪽/오른쪽에 같은 수의 원소.
  • T(n) = 2T(n/2) + n T(n) = **O(n log n)**
  • Worst = 기준의 왼쪽/오른쪽 중 한쪽으로만 원소가 쏠림
  • T(n) = T(n-1) + n T(n) = **O(n^2)**
  • 평균 = 복잡. 다음과 같은 극단적인 경우에도 T(n) = O(n log n)기준을 첫 번째 원소가 아니라 랜덤으로 고름 ?? ← 강의 보기
  • ex) T(n) = T(99n/100) + T(n/100) + n

💡 < 교수님 comment >
수업시간에 Quicksort는 stable하게 구현할 수 있다고 하였습니다.
python으로 예제 코드를 짠 quicksort는 stable하지만,
그림으로 보여준 예는 이 자체만으로는 stable하지 않고 추가적인 작업이 필요합니다.
따라서,
<퀵 정렬>
두 리스트를 사용하는 방법은 stable
추가적인 공간을 사용하지 않으면 복잡함

 

 

힙 정렬

• 버블 정렬과 비슷하며, 1등을 뽑아내고 나머지 원소에서 1등을 또 뽑아내면 정렬됨
• 버블 정렬은 남은 원소에서 1등을 다시 비교로 찾는다면,
  • 힙 정렬은 1등을 뽑아낸 후 나머지 원소에서 1등을 찾을 때 기존의 2등이 자동으로 1등이된다.

힙 생성 → 루트 원소 제거 → 힙을 유지

• 힙(Heap)의 성질
  • 리프 노드를 제외한 모든 노드는 자식이 반드시 2개.
  • 완전이진트리에서 리프 노드가 어떤 노드 이후부터 모두 생략된 형태이다.
  • 부모는 자식보다 반드시 크거나(max heap), 자식보다 반드시 작다(min heap)
  • 트리를 배열로 표현할 수 있다.

• 힙 만들기 시간 복잡도
  • 빈 힙에 차례대로 원소 삽입 : log 1 + log 2 + … + log n ≤ n * log n ⇒ O(n log n)
  • 두 힙을 병합 : T(n) = 2T(n/2) + log n = O(n)

두 힙을 병합하는 과정을 반복 - 시간복잡도