[자료구조 · 알고리즘] 정렬과 탐색 (Sort & Search)

어서와! 자료구조와 알고리즘은 처음이지? 강의 수강 후 내용을 정리한 글입니다.

 

정렬 (Sort)

 

정렬이란, 배열에 있는 원소들을 조건에 따라 정렬한다는 것을 의미한다.

파이썬에서 문자열로 이루어진 리스트를 정렬할 경우, 문자열은 사전 순서를 따르며 길이가 길다고 해서 큰 것이 아니라는 점을 주의해야 한다.

 

파이썬에서의 리스트 정렬 방법은 2가지가 있다.

 

• sorted()

파이썬의 내장 함수 (built-in function)

'새로운' 정렬 리스트를 만듦

 

• sort()

리스트의 method

단순히 해당 리스트를 정렬함

 

L = [3, 8, 2, 7, 6, 10, 9]

L2 = sorted(L)

L.sort()

 

• 역순으로 정렬

reverse=True를 입력함으로써 파이썬의 리스트를 역순으로 정렬한다.

 

 

탐색 (Search)

 

• 탐색 알고리즘(1) - 선형 탐색 (Linear Search)

선형 탐색은 순차 탐색이라고도 불린다.

앞에서부터 뒷까지 하나하나 차례대로 탐색한다.

 

예를 들면 10가지의 서로 다른 숫자 중에서 하나의 숫자를 찾기 위해선, 앞부터 정렬된 숫자들을 순서대로 비교하며 찾는 값을 확인한다.

 

즉 리스트의 길이에 비례하는 시간을 소요하므로 O(n)이다.

찾는 원소가 리스트 앞쪽에 있다면 금방 찾지만, 맨 뒤에 있거나 없을 경우 모든 원소를 다 비교해야 하기에 시간이 오래 걸린다.

 

 

• 탐색 알고리즘(2) - 이진 탐색 (Binary Search)

크기 순으로 정렬되어 있다는 성질을 이용한다.

 

주어진 리스트에서 하나의 원소를 찾기 위해선 가장 낮은 값과 높은 값의 '중간'값을 찾아 비교해나가면 된다.

중간값이 찾는 값보다 작다면, 중간값의 바로 다음 값부터 가장 큰 값까지 중에서 다시 '중간' 값을 찾아 찾는 값과 비교한다.

lower - middle - upper

 

두 범위 사이에서 좁혀나가다 보면 찾는 값을 발견할 수 있다. 이를 '이진 탐색'이라고 한다. (divide & conquer)

빅오 표기법으로는 O(log n)이다.