썸네일 출처: https://m.rpm9.com/20170910090014
정렬
연속된 데이터를 기준에 따라서 정렬하기 위한 알고리즘
선택 정렬
가장 원시적인 정렬 방법.
가장 작은 데이터를 선택해 맨 앞에 있는 데이터랑 바꾸고,
그다음 작은 데이터를 선택해 앞에서 두 번째 데이터랑 바꾸고,
그다음 작은 데이터를 선택해 앞에서 세 번째 데이터랑 바꾸고, ...
파이썬에서는 바꾸는 행위인 스와프의 구현이 간단함.
array = [3, 5]
array[0], array[1] = array[1], array[0]
-----------------------------------------------------------------------------------
print(array) >>> [5, 3]삽입 정렬
데이터를 하나씩 확인하면서, 정렬되어 있는 데이터에서의 위치를 찾아 그 위치에 삽입.
오름차순으로 정렬한다고 하면, 한 칸씩 이동하면서 자기보다 작은 데이터를 만나면 그 자리에서 멈춰버리게 만든다.
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(1, len(array)):
for j in range(i, 0, -1):
if array[j] < array[j - 1]:
array[j], array[j - 1] = array[j - 1], array[j]
else:
break퀵 정렬
교환하기 위한 기준이 되는 피벗을 사용해 리스트를 분할해 나가면서 정렬.
- 리스트의 첫 번째 데이터를 피벗으로 정한다.
- 피벗을 제외하고, 왼쪽부터는 피벗보다 큰 데이터를, 오른쪽부터는 피벗보다 작은 데이터를 찾을 때까지 데이터를 하나씩 확인한다.
- 찾은 두 데이터의 위치를 교환한다.
- 찾은 두 데이터가 엇갈리기 전까지 반복하고, 엇갈리게 되면 작은 데이터와 피벗의 위치를 교환한다.
- 피벗을 제외하고 남은 두 리스트에 대해, 다시 위의 과정을 반복한다.
- 현재 리스트의 데이터 개수가 1이 될 때까지 반복한다.
파이썬으로는 재귀 함수로 구현할 수 있다.
피벗보다 작은 데이터로 구성된 리스트, 피벗보다 큰 데이터로 구성된 리스트로 분할하고 이를 다시 반복하는 형태.
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array):
if len(array) <= 1:
return array
pivot = array[0] # 피벗은 첫 번째 원소
tail = array[1:] # 피벗을 제외한 리스트
left_side = [x for x in tail if x <= pivot]
right_side = [x for x in tail if x > pivot]
return quick_sort(left_side) + [pivot] + quick_sort(right_side)계수 정렬
직접 데이터의 값을 비교한 뒤에 위치를 변경하는 방식이 아니라, 전체 리스트에서 각 데이터의 출현 횟수를 세서 새로운 리스트에 출현 횟수만큼 해당 데이터를 반복해서 출력하는 방식이다.
- 가장 작은 데이터와 가장 큰 데이터가 모두 담길 수 있도록 하나의 리스트를 생성하고, 모든 데이터가 0이 되도록 초기화한다.
- 데이터를 하나씩 확인하면서 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다.
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
count = [0] * (max(array) + 1)
for i in range(len(array)):
count[array[i]] += 1
for i in range(len(count)):
for j in range(count[i]):
print(i)데이터의 크기가 한정되어 있으면 효과적인 방식.
파이썬의 정렬 라이브러리
sorted(): 정렬된 리스트를 반환sort(): 리스트 내장 함수로 별도의 반환 없이 내부 원소가 정렬됨
둘 다 key 매개변수로 함수를 입력해서 정렬 기준을 설정할 수 있다. 여기에는 주로 lambda가 사용된다.
array = [('바나나', 2), ('사과', 5), ('당근', 3)]
result = sorted(array, key=lambda x: x[1])이진 탐색
탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘
순차 탐색
리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례로 확인하는 방법. 지금까지는 거의 이 방법을 사용했고, 원소 개수가 N이면 시간 복잡도는 .
for i in range(n):
...이진 탐색: 반으로 쪼개면서 탐색하기
배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있다.
시작점과 끝점으로 중간점을 정한 다음, 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하는 방식.
파이썬에서 구현은 퀵 정렬에서 처럼 재귀 함수 사용.
def binary_search(array, target, start, end):
if start > end:
return array
mid = (start + end) // 2
if target == mid:
return mid
elif array[mid] > target:
return binary_search(array, target, start, mid - 1)
else:
return binary_search(array, target, mid + 1, end)