2019.03.25 - Algorism - Sort, Search

알고리즘(1) - 정렬(Sort)과 탐색(Search)

정렬과 탐색은 여러 알고리즘들 중에서 가장 많이 사용되는 것 들이다.

정렬(Sort)

정렬은 주어진 데이터들을 정해진 기준에 따라 나열하는 것을 말한다. 이 정렬 알고리즘에는 여러가지가 존재한다. (버블 정렬, 선택 정렬, 삽입 정렬, 셸 정렬, 병합 정렬, 퀵 정렬..)

하지만 파이썬(python)은 자체적으로 list자료형에서 정렬 기능을 함수를 통해 지원한다. 두가지 방법을 통해 정렬을 사용할 수 있는데, 이 두가지 방법에는 작치만 큰 차이가 있다.

1. 파이썬 내장 함수 sorted()
2. 리스트에 쓸 수 있는 메서드 .sort()

일단 1.번 내장 함수 sorted()는 정렬된 새로운 리스트를 리턴시켜준다. 반면 .sort()메서드는 아무것도 리턴하지 않는다(None을 리턴). 따라서 sorted()함수는 원본 리스트에 아무런 영향을 주지않고, .sort()메서드는 원본 리스트 자체를 정렬시킨다.

some_list = [5, 7, 2, 3, 1]
sorted(some_list)
print(some_list)
>>> [5, 7, 2, 3, 1]

some_list.sort()
print(some_list)
>>> [1, 2, 3, 5, 7]

파이썬에서 자체적으로 정렬기능을 지원하지만 그래도 정렬 알고리즘들을 공부해야한다.

탐색(Search)

탐색은 주어진 데이터 안에서 특정한 데이터 또는 원소를 찾는 것을 말한다. 가장 기본적인 탐색에는 선형 탐색(linear search)과 이진 탐색(binary search)이 있다.

1. 선형 탐색은 순차적으로 모든 요소들을 검사하여 원하는 값을 찾는다. 배열의 길이에 따라 찾는데 걸리는 시간이 달라진다. 최악의 경우(맨 끝에 원하는 값이 있는 경우) 배열의 모든 원소를 다 검사해야한다.

def linearSearch(li, key):
    for i in range(len(li)):
        if key == li[i]:
            return i

1. 이진 탐색은 배열이 이미 정렬되어있는 경우를 가정하고 적용한다. 이진 탐색은 주어진 정렬된 데이터에서 반을 나눠 가운데 값과 찾으려는 원소의 값의 크기를 비교한다. 이를 통해 찾고자 하는 값이 가운데 값의 오른쪽에 있는지, 왼쪽에 있는지를 판단한다. 이러한 과정을 반복하다보면 가운데 값과 원하는 원소가 일치하는 순간이 탐색이 종료되는 시점이 된다.

def binarySearch(li, key):
	low = 0
	high = len(li) - 1
	
	while high >= low:
		mid = (low + high) // 2
		
		if key < li[mid]:
			high = mid - 1
			
		elif key == li[mid]:
			return mid
		
		else:
			low = mid + 1

	return -1  # not found