3강: 정렬(sort)과 탐색(search)

-정렬이란?
복수의 원소로 주어진 데이터를 정해진 기준에 따라 새로 늘어놓는 작업.
1. 파이썬 내장 함수 sorted()
2. 리스트에 쓸 수 있는 메서드 .sort()

-수치가 아닌 데이터형의 정렬?
문자열을 사전에 등장하는 순서에 따라 정렬. 여러 데이터를 복합으로 이루어진 데이터 원소를 보통(데이터베이스에서) 레코드(record)라 부름.

-탐색이란?
복수의 원소로 이루어진 데이터에서 특정 원소를 찾아내는 작업.
1. 선형탐색(linear search) 또는 순차탐색(sequential search): 순차적으로 모든 요소들을 탐색하여 원하는 값을 찾아냄. 배열의 길이에 비례하는 시간이 걸리므로, 최악의 경우에는 배열에 있는 모든 원소를 검사해야할 수도 있음.
2. 이진탐색(binary search): 탐색하려는 배열이 이미 정렬되어 있는 경우에만 적용가능. 배열의 가운데 원소와 찾으려 하는 값을 비교하면(크기 순으로 정렬되어 있다는 성질을 이용) 왼쪽에 있을지 오른쪽에 있을지를 알 수 있음. 그 특징으로 반열의 반을 줄여나가면서 탐색하지 않고 버릴 수 있음. 이 과정을 반복하여 원하는 값을 찾아낼 수 있음.