[Algorithm] 검색, 정렬

1. 검색

1) 순차검색

 

정렬되지 않은 자료의 검색과정

- 첫번째 원소부터 순서대로 검색대상과 키 값이 같은 원소가 있는지를 비교하여 찾음
- 키 값이 동일한 원소를 찾으면 그 원소의 인덱스를 반환
- 자료구조의 마지막에 갈 때 까지 검색 대상을 찾지 못하면 검색 실패

찾고자 하는 원소의 순서에 따른 비교횟수 결정

- 첫 번째 원소를 찾을 떄에는 1번 비교, 두 번째 원소를 찾을 때에는 2번 비교
- 정렬되지 않은 자료에서의 순차 검색의 평균 비교 횟수 (n+1)/2
- 시간 복잡도는 O(n)

def sequentialSearch(a,n,key):
    i = 0
    while i < n and a[i] != key:
        i += 1
    if i < n:
        return i
    else:
        return -1

정렬된 자료의 검색과정

- 자료가 오름차순으로 정렬된 상태에서 검색을 실시한다고 가정
- 자료를 순차적으로 검색하면서 키 값을 비교함
- 원소의 키 값이 검색 대상의 키 값보다 크면 원소가 없다는 것이므로 더 이상 검색하지 않고 검색을 종료함

 

찾고자 하는 원소의 순서에 따른 비교횟수 결정

- 정렬되어 있으므로, 검색 실패를 반환하는 경우 평균 비교 회수가 반으로 줄어듦
- 시간 복잡도 : O(n)

 

def sequentialSearch2(a,n,key):
    i = 0
    while i < n and a[i] < key:
        i = i + 1
    if i < n and a[i] == key:
        return i
    else:
        return -1

 

2) 이진 검색

- 효율적인 검색 방법
- 자료의 가운데 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속하는 방법
    - 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 빠르게 검색을 수행함
- 이진 검색을 하기 위해서는 자료가 정렬된 상태여야함
- 정렬된 데이터 n개가 있는 경우의 시간복잡도
    - 순차 검색 시 O(n)의 시간이 걸리지만, 이진 검색 시 O(logN)의 시간이 걸림

 

이진 검색의 검색과정

1. 자료의 중앙에 있는 원소를 선택
2. 중앙 원소의 값과 찾고자 하는 목표 값을 비교
3. - 목표값 < 중앙원소값: 자료의 왼쪽 반에 대해서 새로 검색을 수행
   - 목표값 > 중앙원소값: 자료의 오른쪽 반에 대해서 새로 검색을 수행
4. 찾고자하는 값을 찾을 때까지 [1~3]의 과정을 반복

 

이전 검색의 구현

- 검색 범위의 시작점과 종료점을 이용하여 검색을 반복수행함
- 이진 검색의 경우, 자료에 삽입이나 삭제가 발생하였을 때 List의 상태를 항상 정렬 상태로 유지하는 추가 작업이 필요함

 

def binarySearch(a, key):
    start = 0
    end = len(a)-1
    while start <= end:
        middle = start + (end-start) // 2
        if key == a[middle]:
            return True
        elif key < a[middle]:
            end = middle-1
        else:
            start = middle+1
    return False

# 재귀 함수를 이용한 이진 검색 구현

def binarySearch2(a, low, high, key):
    if low > high:
        return False
    else:
        middle = (low + high) // 2
        if key == a[middle]:
            return True
        elif key < a[middle]:
            return binarySearch2(a, low, middle-1,key)
        elif a[middle] < key:
            return binarySearch2(a, middle+1, high, key)

3) 인덱스

- 데이터 베이서에서 유래, 테이블에 대한 동작 속도를 높임
- 룩 업 테이블 등의 용어로 사용함
- 인덱스를 저장하는데 필요한 디스크 공간은 보통 테이블 저장에 필요한 디스크 공간 보다 작음
    - 인덱스는 키-필드만 갖고 있고, 테이블의 다른 세부 항목은 갖고 있지 않음
- List를 사용한 인덱스
    - 대량의 데이터를 매번 정렬하면, 프로그램의 반응은 느려질 수 밖에 없음. 이러한 대량 데이터의 성능 저하 문제를 해결하기 위해 List 인덱스를 사용할 수 있음


※ 원본데이터에 데이터가 삽입될 경우 상대적으로 크기가 작은 인덱스 List를 정렬하기 때문에 속도가 빠름

 

2. 정렬

셀렉션 알고리즘 의미

- 저장되어 있는 자료로부터 k번째로 큰 혹은 작은 원소를 찾는 방법
- 최소값, 최대값 혹은 중간값을 찾는 알고리즘을 의미하기도 함

셀렉션 선택 과정

- 정렬 알고리즘을 이용하여 자료를 정렬
- 원하는 순서에 있는 원소 가져오기

 

# k번째로 작은 원소를 찾는 알고리즘
"""
- 1번부터 k번째까지 작은 원소들을 찾아 List의 앞쪽으로 이동시키고, List의 k번째를 반환
- k가 비교적 작을 때 유용하며 O(kn)의 수행시간을 필요로 함
"""


def select(list, k):
    for i in range(0, k):
        minIndex = i
        for j in range(i+1, len(list)):
            if list[minIndex] > list[j]:
                minIndex = j
        list[i], list[minIndex] = list[minIndex], list[i]
    return list[k-1]

 

1) 선택정렬 

예시) 포켓볼 순서대로 정렬하기

 

선택 정렬의 의미

- 주어진 자료들 중 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식
- 셀렉션 알고리즘을 전체 자료에 적용한 것

 

정렬 과정

- 주어진 List 중에서 최소값을 찾음
- 그 값을 List의 맨 앞에 위치한 값과 교환
- 맨 처음 위치를 제외한 나머지 List를 대상으로 위의 과정을 반복

※ 시간 복잡도 O(n**2)

 

def selectionSort(a):
    for i in range(0, len(a)-1):
        min = i
        for j in range(i+1, len(a)):
            if a[min] > a[j]:
                min = j
        a[i], a[min] = a[min], a[i]

 

 

이 포스트는 SW Expert Academy(https://swexpertacademy.com/)에서 파이썬 SW문제해결 기본을 들으며 정리한 내용입니다.