2. 정렬(Sorting)

지난 학기 학교 알고리즘 수업을 수강하며, 정리 해 놓았던 마크다운 문서입니다. 문제시 삭제하겠습니다

• Insertion sort / O(n^2)
• Quick sort / O(n^2) (기대 수행시간 : O(nlogn))
• Merge sort / O(nlogn)
• Heap sort / O(nlogn)
• Radix sort / O(n) (input에 특정 제한사항이 있을경우, O(n)에 수렴)

Insertion Sort

• 인덱스 0은 정렬된 상태라 가정(sorted segment), 나머지 요소들은 (unsorted segment)
• 인덱스 1 x라 하면 일단 밖으로 빼고 인덱스1 vacancy로 남겨둠(빈공간)
• x가 sorted segment보다 작으면 swap
• n-1번 반복

• loop invariant 분석방법 (수학적 귀납법과 유사)
  1. Initalization - 알고리즘이 loop에서 첫번째 iteration 수행전에 그 알고리즘이 어떤 속성 만족시켜야함
  2. Maintenance - loop에서 어떤 iteration 수행전에 참이면 다음 iteration 수행도 참
  3. Termination - 모든 loop 가 종료되고, 알고리즘이 정확히 수행됬음을 보여줘야함

• insertion sort 에 적용
  1. index 0 - 초기화 단계, 정렬된 상태이다
  2. 어느 한 인덱스에서 loop 수행하면 정렬된 상태 만족
  3. 모든 loop 끝나면 정렬상태 만족

def insertion_sort(arr):
    n=len(arr)
    for i in range (1, n):
        # i 번 위치의 값을 key로 저장
        key=arr[i]
        # j를 i 바로 왼쪽 위치로 저장
        j=i-1
        #리스트의 j번 위치의 값과 key를 비교해 key 삽입 위치 찾기
        while j>=0 and arr[j]>key:
            arr[j+1]=arr[j] # 삽입할 공간 생기도록 값을 오른쪽 한칸 이동
            j-=1
        arr[j+1]=key # 찾은 삽입 위치에 key를 저장
        
data=[2,4,5,1,3]
insertion_sort(data)

print(data)

Insertion Sort : 분석

• Worst Case Complexity

  어떤 index i에 x가 있다면 최악의 경우 앞에 있는 모든 원소들과 비교하는 경우

  

• Average behavior

  각각의 i에 대한 shiftVacRec 함수의 기본연산수가 핵심

  

  이런 자료형이라고 가정하면 index 5부터 0까지의 비교연산은 1, 2, 3, 4, 5, 5이다 (인덱스 0,1은 비교연산수 동일)
  따라서 index 0에서는 하나의 비교연산 case가 존재하고 index 1~5까지의 경우에는 i cases의 비교연산이 존재한다 -> 총 i+1

  각 케이스 일어날 확률 모두 같다고 가정하므로 1/(i+1), index 0에선 앞에있는 모든 원소와 비교 해야 하므로, i번의 비교연산 수행 -> i/(i+1)

  따라서

  

오직 인접한 element끼리 교환 할때만 optimal 하다고 볼수 있다. (순차접근), 최선의 정렬 알고리즘은 아님

Qucik Sort

Worst case : Θ(n^2), but 일반적인 경우 가장 빠름 (평균 Θ(nlogn))

divide and conquer (분할정복법)

어떤 문제를 해결할 때 여러개의 작은 문제로 쪼개서 해결하기

1. divide (어떤 문제 여러개의 문제로 쪼개기)
2. conquer (서브 문제들 푸는 단계, 대개 재귀적으로 품 )
3. combine (서브 문제들 해결법 합쳐주는 단계)

Quick sort

divide and conquer와 randomization 전략 사용

n개의 원소중에 임의의 원소 선택 (pivot)

pivot을 기준으로 세개의 그룹으로 나눠줌

• L - pivot보다 작은 원소들
• E - pivot과 같은 원소들
• G - pivot 보다 큰 원소들

위와같이 계속 재귀적 수행

partition(S, p)
//자료형 리스트라고 가정(배열도 가능(환형배열))

    Input: sequence S, position p of pivot
    Output: subsequences L, E, G of the
        elements of S less than, equal to,
        or greater than the pivot, resp.
    L, E, G <- empty sequences
    x <- S.remove(p) // O(1) time
    while !S.isEmpty() // O(n) iterations
        y <- S.remove(S.first()) // O(1) time
        if y < x
            L.insertLast(y) // O(1) time
        else if y = x
            E.insertLast(y) // O(1) time
        else { y > x }
            G.insertLast(y) // O(1) time
    return L, E, G

• Worst case

  pivot이 가장 작은 값이거나 가장 큰 값으로 선택된

  L 이나 G는 n-1의 사이즈 가지게 되고 다른 하나는 0 일것

  

  피벗 e를 제외한 나머지 원소 n-1, n-2, ... 2, 1번의 비교 연산 수행

  따라서 n+(n-1)+...+2+1 -> O(n^2) worst case

Outline of average case analysis for quick sort (informal analysis)

• 다음과 같이 정렬된 배열이 있다 했을 때 best의 경우는 pivot이 가운데 위치하는 경우 (2/n 지점)

• 그럼 average의 경우는 best와 worst case 중간지점 쯤 되는 경우라고 볼 수 있다 n/4과 3n/4 각각 지점

• L : G 그룹이 있으면 1 : 3의 비율로 partition 된다 가정 (n/4, 3n/4)

• 가정에 의해 l g 그룹으로 나누면 이런 형식으로 남은 원소가 1이 될때까지 나눌것임 (g쪽이 더 길게)

• 각각의 level에서 partition O(n)에 수행

• 가장 깊은 height k라 하고 구하기 (g라인)

• n 에서 3/4를 얼만큼 곱해야 1이 될까?

따라서 k <= c * logn 를 만족하는 c가 존재할것임 -> 트리의 height : θ(logn)에 bound

그러므로 총 알고리즘 평균시간 O(nlogn) time 이라고 볼 수있다

(꼭 1:3으로 하지않고 1:9, 1:99 등으로 해도 성립함)

In-place Quick sort

In-place : space를 적게 사용하는 경우를 말함 (additional O(1) space)

O(logn)도 재귀의 경우에선 in-place라고 허용해줌

Algorithm inPlaceQuickSort(S, l, r)
    Input sequence S, ranks l and r //rank : index 라고 생각
    Output sequence S with the
        elements of rank between l and r
        rearranged in increasing order
    if l >= r
        return
    i <- a random integer between l and r
    x <= S.elemAtRank(i)
    (h, k) <- inPlacePartition(x)
    inPlaceQuickSort(S, l, h - 1) // L 그룹에 대한 재귀
    inPlaceQuickSort(S, k + 1, r)// G 

랜덤으로 피벗 i를 고름

L 그룹 (l : h-1), E 그룹(h : k), G그룹 (k+1, r)로 분할 가능

in-place partitioning

• L그룹과 E U G 그룹으로 partition
  

• 밑의 과정 j과 k 가 만날때까지 반복

  1. j를 pivot 보다 크거나 같은값 만날때까지 오른쪽으로 찾기
  2. k를 pivot 보다 작거나 같은값 만날때까지 왼쪽으로 찾기
  3. j, k swap

계속 하다보면 j와 k는 9에서 만나게됨, 마지막으로 9와 pivot 6의 위치를 swap해준다

j 와 k 만난 index를 경계로 왼쪽에는 pivot보다 작은 수들이 오른쪽에는 pivot보다 큰 수들과 pivot이 위치 하게됨 (L과 E U G 로 파티션)

(상수 크기의 O(1) space이용해서 파티션 수행가능)