이중 탐색 Binary Search, 퀵 정렬 Quick Sort

이진 검색

---

이진 검색 Binary Search

• 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법
  목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행함
• 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다

검색 과정

1. 자료의 중앙에 있는 원소를 고른다
2. 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다
3. 중앙 원소의 값과 찾고자 하는 목표 값이 일치하면 탐색을 종료한다
4. 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행한다
5. 찾고자 하는 값을 찾을 때까지 1~4의 과정을 반복한다

알고리즘: 반복구조

binarySearch (S[], n, k)
low = 0
high = n-1
WHILE low <= high
    mid = (low+high) / 2
    IF S[mid] == key
        RETURN mid
    ELSE S[mid] > key
        high = mid-1
    ELSE
        low = mod + 1
RETURN -1

알고리즘: 재귀구조

binarySearch(S[], low, high, key)
    IF low > high
        RETURN -1
    ELSE
        mid = (low+high)/2
        IF key == S[mid]
            RETURN mid
        ELIF key < S[mid]
            RETURN binarySearch(S[], low, mid-1, key)
        ELSE
            RETURN binarysearch(S[], mid+1, high, key)

퀵 정렬

---

• 주어진 배열을 두 개로 분할하고, 각각을 정렬한다
  • 병합 정렬과 동일?
• 다른 점 1: 병합 정렬은 그냥 두 부분으로 나누는 반면에, 퀵 정렬은 분할할 때, 기준 아이템 (pivot item) 중심으로, 이보다 작은 것은 왼편, 큰 것은 오른편에 위치시킨다
• 다른 점 2: 각 부분 정렬이 끝난 후, 병합 정렬은 “병합”이란 후처리 작업이 필요하나, 퀵 정렬은 필요로 하지 않는다
• 불안정 ㅈ어렬
• 시간 복잡도 O(nlogn), 최악의 경우 O(n^2)

동작 과정

1. 정렬한 배열 입력
2. 임의의 한 점을 pivot으로 선정 (Partition 방법)
3. → pivot 보다 작은 값들을 왼쪽으로, 큰 값들은 오른쪽으로 이동
4. 정렬할 범위가 0이나 1이 될 때까지 분할 정복

알고리즘

quickSort(A[], l, r)
    if l < r
        pivot = partition(a, l, r)
        quickSort(A[], l, pivot-1)
        quickSort(A[], pivot+1, r)

Hoare-Partition 알고리즘

Hoare-Partition(arr[], left, right) {
    pivot = arr[left] // 제일 왼쪽 값 pivot
    L = left+1
    R = right
    while (L<=R) {
        while (L<=R and arr[L] <= pivot) L++
        while (arr[R] > pivot) R--
        if (L<R)
            swap(arr[L], arr[R])
    }
    swap(arr[left], arr[R])
    return R
}

Lomuto partition 알고리즘

Lomuto-Partition(arr[], left, right) {
    pivot = arr[right]
    i = left-1

    FOR j in left → right - 1
        IF arr[j] <= pivot
            i++
            swap(arr[i], arr[j])
    swap(arr[i+1], arr[right])
    RETURN i+1
}