파이썬) 정렬(sort)과 탐색(search)

정렬이란 여러 원소로 주어진 데이터를 정해진 기준에 맞게 늘어놓는 작업을 말한다. 그중 대표적으로 sort가 있는데 파이썬에는 함수 sorted()와 메소드 .sort()가 있다. 이 둘의 차이점을 예시로 통해 보여주자면

 

a=[5,7,3,9,1]
a.sort()
a

[1, 3, 5, 7, 9]

임의의 리스트 a를 a.sort()를 이용한 후 a를 출력하면 오름차순으로 정렬된 결과가 나온다. 

 

a=[5,7,3,9,1]
sorted(a)
a

[5, 7, 3, 9, 1]

하지만 sorted(a)를 이용한 후 a를 출력하면 a는 그대로 출력되는 것을 볼 수 있다.

 

이처럼 sort는 기본적으로 오름차순으로 데이터들을 정렬하고, 그 외 정렬 기준을 여러 코드를 이용해 설정할 수 있다.

 

 

 

 

탐색이란 여러 원소로 이루어진 데이터에서 특정 원소를 찾아내는 방법이다. 그 중 기본적인 방법 두가지를 소개하자면 

 

1. 선형 탐색 : 순차적으로 모든 요소들을 탐색하여 원하는 값을 찾아내는 방법이다. 배열의 길이에 비례하는 시간이 걸리므로, 최악의 경우에는 배열에 있는 모든 원소를 다 검사해야 할 수 있다.

 

2. 이진 탐색 : 배열의 시작과 끝, 중간값을 이용해 원하는 값을 찾아내는 방법이다. 이때 배열은 이미 정렬되어 있어야 한다.실행 알고리즘을 그림을 통해 표현하자면 

 

위와 같이 임의의 배열이 있고 7을 찾고자 이진 탐색을 사용한다고 할 때,  시작과 끝, 중간값을 설정한다. 첫 단계에서 중간값 4는 7보다 작으므로 4이하인 원소들은 날리고 다음 인덱스 값 5를 새로운 시작값으로 바꾼다.

 

그렇게 되면 중간값은 6으로 바뀌고 끝값은 그대로이다. 두번째 단계에서도 첫번째 단계와 마찬가지로 중간값과 목표값을 비교한다. 중간값 6은 7보다 작으므로 6이하 원소들을 날리고 7을 새로운 시작값으로 바꾼다.

 

다음 단계에서 시작값은 7, 중간값도 7, 끝값은 8이된다. 여기서 중간값7과 찾고자 하는 값7과 같으므로 탐색을 마치게 된다. 

 

만약 위 과정을 선형 탐색을 이용한다면 단계는 많아지고 실행속도는 느려질 수 있다. 이진 탐색이 선형 탐색보다 빠른 방법이긴 하지만 이진 탐색은 리스트가 정렬되어 있어야한다는 가정이 있고, 제시된 문제에 따라 무조건 이진탐색이 더 빠르다는 보장은 없다. 이는 자료구조에 대해 좀 더 공부하고 어떤 탐색이 최적의 알고리즘을 만들게 해주는지 알아야 한다.