정렬과 이분 탐색

정렬

데이터를 특정한 기준에 따라 순서대로 나열하는 것을 정렬(Sort)이라 한다. 프로그램에서는 데이터를 효율적으로 가공하거나 활용하기 위해 먼저 정렬을 수행하는 경우가 많다. 아래는 프로그램에서 사용되는 대표적인 정렬 알고리즘들이다.

선택 정렬: O(N^2). 앞에서부터 차례대로 가장 작은 원소를 찾아 현재 위치에 놓는 방식이다.
삽입 정렬: O(N^2). 원소를 하나씩 선택해, 이미 정렬된 부분에 적절한 위치에 삽입하는 방식이다.
퀵 정렬: O(N log N) (최악의 경우 O(N^2)). 피벗을 기준으로 원소들을 분할하고, 피벗을 기준으로 작은 값과 큰 값을 서로 교환하여 정렬한다. 분할된 부분에 대해 재귀적으로 정렬을 반복한다.

정렬 예시 코드

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

# 선택 정렬
def selection_sort(array, n):
    for i in range(n):
        idx = i
        for j in range(i + 1, n):
            if array[idx] > array[j]:
                idx = j
        array[i], array[idx] = array[idx], array[i]

# 삽입 정렬
def insertion_sort(array, n):
    for i in range(1, n):
        for j in range(i, 0, -1):
            if array[j - 1] > array[j]:
                array[j - 1], array[j] = array[j], array[j - 1]
            else:
                break

# 퀵 정렬
def quick_sort(array, start, end):
    if start >= end:
        return
    pivot = start
    left, right = start + 1, end
    while left <= right:
        # 피벗보다 큰 데이터를 찾을 때까지 반복
        while left <= end and array[left] <= array[pivot]:
            left += 1
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while right > start and array[right] >= array[pivot]:
            right -= 1
        if left > right:  # 엇갈렸다면 작은 데이터와 피벗을 교체
            array[right], array[pivot] = array[pivot], array[right]
        else:  # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            array[left], array[right] = array[right], array[left]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)

selection_sort(array, len(array))
# or
insertion_sort(array, len(array))
# or
quick_sort(array, 0, len(array) - 1)

print(array)

Python에서의 정렬

파이썬의 list는 기본적인 정렬 메서드를 포함한다. 병합 정렬(Merge Sort)과 삽입 정렬(Insertion Sort)을 혼합한 방식으로, 평균적으로 O(N log N)의 시간 복잡도를 가진다.

대부분의 경우에서 매우 효율적이며, 짧은 코드로도 정렬이 가능해 문제에서 별도의 정렬 알고리즘 구현 방식을 요구하지 않는 경우 sort 메서드의 사용으로 쉽게 데이터를 정렬할 수 있다.

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
array.sort()

print(array)

메서드의 인자 값을 설정하여 정렬 기준을 쉽게 변경할 수도 있다. 아래는 원소의 두 번째 값을 기준으로 (오름차순) 정렬 후, 이를 역순으로 뒤집어 내림차순 정렬한 코드이다. (기본 정렬 인자에 대해)

array = [('마리오', 171), ('루이지', 177), ('키노피오', 153)]
array.sort(reverse=True, key=lambda x: x[1])

print(array)

이진 탐색

이진 탐색(Binary Search, 또는 이분 탐색)은 정렬된 데이터에서 특정 값을 빠르게 찾는 알고리즘이다. 데이터를 절반씩 나누어가며 탐색 범위를 좁혀 나가는 방식으로, 각 단계에서 탐색 범위를 반으로 줄이기 때문에 시간 복잡도는 O(log N)이다.

이진 탐색의 동작 방식은 다음과 같다:

배열의 중간 값을 선택한다.
찾고자 하는 값이 중간 값보다 작으면 왼쪽을, 크면 오른쪽을 선택한다.
대상 값을 찾을 때까지 위 과정을 반복

이진 탐색은 정렬된 배열에서만 사용할 수 있으며, 정렬되지 않은 배열에서 사용할 경우 먼저 정렬을 해야 한다.

순차 탐색과의 비교

순차 탐색(Sequential Search)은 리스트의 가장 앞에서부터 하나씩 원소를 확인하며 특정 값을 찾는 알고리즘이다. 모든 원소를 확인하므로 정렬되지 않은 리스트에서도 값을 찾을 수 있지만, 시간 복잡도가 O(N)으로 이진 탐색과 비교했을 때 상대적으로 속도가 느리다.

이진 탐색 예시 코드 (1) - 재귀 함수

array = [ ... ]

def binary_search(array, target, start, end):
    if start > end:
        return -1
    mid = (start + end) // 2
    if array[mid] == target:
        return mid
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    else:
        return binary_search(array, target, mid + 1, end)

result = binary_search(array, target, 0, len(array) - 1) + 1
print(result + 1 if result >= 0 else '값이 없음')

이진 탐색 예시 코드 (2) - 반복문

array = [ ... ]

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None

result = binary_search(array, target, 0, len(array) - 1) + 1
print(result + 1 if result >= 0 else '값이 없음')