본문 바로가기
Topos Uranos
한국어

탐색과 정렬

요약

탐색과 정렬은 컬렉션에 관한 두 가지 기본 문제이며, 둘 사이에는 맞바꿈이 있다. 정렬은 한 번 비용이 들지만, 그 뒤의 탐색을 하나하나 싸게 만든다. 이 수업은 선형 탐색과 이진 탐색을 손으로 쓴다. 이진 탐색은 정렬된 데이터에서 단계마다 절반을 버린다. 이진 탐색을 불변식으로 정당화하고, 끝난다는 것을 증명하고, 회차 수를 세고, 그것을 망치는 세 가지 오류를 살펴본다. 이어서 선택 정렬과 삽입 정렬을 각각의 불변식과 비교 횟수의 정확한 계산과 함께 다루고, 그 뒤에 같은 문제를 범위 라이브러리로 풀며, 탐색하기 전에 정렬하는 것이 언제 유리한지를 결정하는 계산을 한다.

학습 목표

  1. 선형 탐색과 이진 탐색을 구현하고, 이진 탐색을 불변식(“값이 있다면 low와 high 사이에 있다”)으로, 끝난다는 증명과 함께 정당화한다.
  2. 선택 정렬과 삽입 정렬을 구현하고, 각각의 불변식을 진술하며, 최선의 경우와 최악의 경우의 비교 횟수를 센다.
  3. 적절할 때 직접 만든 버전 대신 std::ranges::sort, std::ranges::contains, std::ranges::find, std::ranges::binary_search, std::ranges::lower_bound 함수를 그 사전 조건을 지키며 사용한다.
  4. 예상되는 탐색 횟수에 따라, 데이터에서 탐색하기 전에 정렬하는 것이 유리한지 결정하고, 그 결정을 비교 횟수의 계산으로 정당화한다.

선형 탐색

탐색이란 컬렉션과 값이 주어졌을 때 그 값이 있는지, 있다면 어디에 있는지에 답하는 것이다. 데이터의 순서에 관한 정보가 없으면 하나씩 살펴보는 것 말고는 방법이 없다. 이것이 선형 탐색이다. 값이 없을 때 이 강좌에서는 values.size() 값을 반환한다. 이는 벡터에 속하지 않는 첫 위치로, 유효한 인덱스가 아니므로 답과 혼동되지 않으며, 5절에서 보겠지만 라이브러리가 따르는 것과 같은 약속이다.

C++ 프로그램
#include <cstddef>#include <print>#include <vector>​// 사전 조건: 없음.// 사후 조건: values[i] == target을 만족하는 가장 작은 인덱스 i를 반환하고,// target이 없으면 values.size()를 반환한다.std::size_t linearSearch(const std::vector<int>& values, int target){    // 불변식: target은 values[0], ..., values[i - 1] 가운데 없다.    for (std::size_t i{0}; i < values.size(); ++i) {        if (values[i] == target) {            return i;        }    }    return values.size();}​int main(){    const std::vector<int> codes{405, 112, 318, 207, 112, 530};    for (const int target : {207, 112, 999}) {        const std::size_t pos{linearSearch(codes, target)};        if (pos == codes.size()) {            std::println("{}: 없음", target);        } else {            std::println("{}: 위치 {}", target, pos);        }    }}
출력
207: 위치 3112: 위치 1999: 없음

정확성은 10행의 불변식이 보장한다. 처음에 i 변수가 0일 때, 불변식은 빈 부분에 관해 무언가를 주장하므로 참이다. 어떤 회차를 시작할 때 성립하고 values[i] 원소가 찾는 값이 아니면, 그 회차가 끝날 때 원소가 하나 늘어난 채로 성립한다. 그런데 반복문에는 출구가 두 개 있다. return i; 문장이 실행되면 values[i] 원소가 찾는 값이고, 불변식에 의해 그 앞의 어떤 원소도 찾는 값이 아니었으므로, i 변수의 값이 첫 출현 위치이다(그래서 두 번 나타나는 112는 위치 1로 보고된다). 반복문이 조건 때문에 끝나면 i 변수의 값은 values.size() 값과 같고, 불변식은 값이 어디에도 없다고 말한다. 반복문 안의 return 문장은 함수를 끝내고, 그와 함께 반복문도 끝내므로 플래그가 필요 없다.

비용은 알고리즘의 비용 수업의 의미로, 비교 values[i] == target 횟수로 잰다. 값이 없으면 비교는 정확히 nn번, 원소마다 한 번씩 일어난다. 이것이 최악의 경우이다. 값이 위치 pp에 있으면 p+1p + 1번 일어난다. 따라서 선형 탐색은 O(n)O(n) 비용이다. 데이터가 두 배면 일도 두 배이다. 추가 정보가 없으면 더 잘할 수 없다. 어떤 원소를 보지 않고 넘어가는 알고리즘은 값이 거기에 있었는지 알 수 없기 때문이다.