Sorting - Insertion Sort / Quick Sort

- Unsorted data에서 key값을 찾는 데는 θ(n) 비교, Sorted data에서 key값을 찾는 데는 θ(logn) 비교가 필요하다. 따라서 Sorting이 중요하다.

 

1. Insertion Sort

• 인덱스 1부터 시작해 인덱스를 키워가며 앞의 값들과 비교해서 맞는 위치에 끼워 넣음. sorted segment 영역을 늘려간다. i번째 원소의 값이 i-1번째 값보다 작으면 위치 교환, 바뀐 i-1번째 값이 i-2번째 값보다 작으면 교환, 인덱스 0까지 반복.
• Input: n>=1인 배열 E, 인덱스 범위는 0~n-1
• Output: 오름차순 정렬된 배열 E
•  Loop invariant (루프 불변): 알고리즘의 correctness 증명법. 다음의 세 가지를 증명한다.
  1. Initialization: 루프의 첫 번째 iteration이 수행되기 전에 어떤 조건이 true라는 것을 보임
     ex) Insertion Sort에서, index 0에서는 정렬되었다는 가정을 만족함을 보인다.
  2. Maintenance: 특정 iteration이 수행되기 전에 어떤 조건이 true라면, 그다음 iteration이 수행되기 전에도 true이다.
     ex) Insertion Sort에서, index 3에 대해 iteration을 수행하기 전에 0~2번 값들은 정렬되어 있다.
  3. Termination: loop가 끝났을 때, 알고리즘이 정확히 수행되었음을 보여야 한다.
     ex) Insertion Sort에서, 모든 iteration이 끝나고 나면 전체 배열이 오름차순으로 정렬된다.
• Worst-Case Complexity: W(n)=1+2+...+(n-1) = n(n-1)/2 ≈ θ(n^2)
• Average: 1(i+1)*∑(j=1부터 i까지)j + 1/(i+1) = i/2+1-1/(i+1)
  ex) i=4일 때 해당 인덱스의 값을 x라 하자. x가 놓일 수 있는 자리는 다음의 5가지이다.
  1) E[4] 자리 -> [3]과 한 번의 비교만 하면 됨. x가 E[3]보다 큰 경우.  => 1번의 비교연산
  2) E[3] 자리 -> [3]보다 작고, [2]보다 큰 경우.  => 2번의 비교연산
  3) E[2] 자리 -> [3], [2]보다 작고, [1]보다 큰 경우.  => 3번의 비교연산
  4) E[1] 자리 -> [3], [2], [1]보다 작고, [0]보다 큰 경우.  => 4번의 비교연산
  5) E[0] 자리 -> [3], [2], [1], [0]보다 작은 경우.  => 4번의 비교연산.
   따라서 1/(4+1)에 ∑(1부터 4까지) 를 곱하고, 뒤에 1/(4+1) * 4를 더해준 것이다. 5)는 5번의 비교연산이 아닌 4번이므로.
  -> A(n) = ∑(i=1부터 n-1까지){i/2+1-1/(i+1)} ≈ n^2/4 이다.
• Insertion Sort 알고리즘은 random access가 아닌 경우에 optimal.

 

2. Quick Sort

• Divide and Conquer / Randomization 두 가지 전략을 사용한다.
• 1) Divide and Conquer: 여러 개의 작은 subprob로 나눈 뒤 각각 해결(재귀/반복)하고 합친다.
    (1) Divide: 랜덤 x(pivot)을 고르고 x에 따라 기존의 S를 L, E, G로 나눔 (x를 기준으로 작은 건 L로, 큰 건 G로 옮김)
    (2) Conquer: L과 G를 각각 정렬
    (3) Combine: L, E, G를 join
• Worst-case Runninng Time: 최악의 경우는 피봇이 제일 작거나 제일 커서 L또는 G에 모든 원소들이 몰리는 것. 이 경우, n-1사이즈인 그룹에 대해 n-1번 비교, 그 뒤에도 몰리면 n-2사이즈에 대해 n-2번 비교, ... 반복. 즉, O(n^2).
• Average-case Runinng Time: (트리의 각 레벨에서의 수행시간(O(n))*가장 긴 depth) ∈ θ(nlgn)

2-1. In-Place Quick Sort

• pivot보다 작은/큰 부분을 옮기지 않고, 같은 배열 내에서 나누는 방법.
• L: l~h-1인덱스, E: l~k인덱스, G: k+1~r 인덱스.
• l~h-1과 k+1~r 범위에 대해 Sort하면 됨.
• 시작인덱스를 증가시키고 끝인덱스는 감소시키면서 앞쪽에 pivot보다 큰 값과 뒤쪽에 pivot보다 작은 값을 교환한다. 반복하다가 마지막 원소와 pivot을 교환한다. 그러면 pivot을 기준으로 작은 값들/큰 값들로 나뉘게 된다.