오늘은 Python의 탐색과 정렬의 알고리즘에 대해 공부해 보도록 하겠습니다.
탐색
선형탐색(순차 탐색)(Sequential Search)
선형 탐색(Sequential Search)이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 비교하는 방법입니다. == (n, n + 1인덱스)
데이터가 정리되어 있지 않을 경우 많이 사용되지만, 하나씩 직접 비교하기 때문에 시간 복잡도
O(n)이기 때문에 이진 탐색에 비해서 시간 복잡도의 효율은 이진 탐색에 비해 좋지 않습니다.
이진 탐색(Binary Search)
이진 탐색(Binary Search)이란 배열 내부의 테이터가 정렬 되어있어야 사용 가능한 알고리즘입니다.
시간복잡도는 O(log n)입니다. 선형탐색에 비해 효율이 좋기에 빠르게 데이터를 찾을 수 있습니다. 이진 탐색은 탐색 범위를 반으로 좁혀가며 데이터를 탐색합니다.
이진 탐색은 시작점, 끝점, 중간점 3가지 변수가 필요합니다.
사용 방법은 코드와 함께 더욱 자세히 알아보도록 하겠습니다.
정렬
거품 정렬(버블정렬)(bubble sort)
거품 정렬(bubble sort)이란 매번 연속된 두개 인덱스를 비교하여, 정한 기준의 값을 뒤로 넘겨 정렬하는 방법입니다.
오름차순으로 정렬 할 경우,비교시마다 큰 값이 뒤로 이동하여, 1바퀴 돌면 가장 큰 값이 마지막 인덱스에 저장됩니다. 가장 큰 값이 맨 뒤 저장되기 때문에, (전체 배열 크기 - 순환 바퀴 수)만큼 반복해 주면 됩니다. 시간 복잡도는 O(n^2)입니다.
선택 정렬(selection sort)
선택 정렬(selection sort)이란 현재 위치에 들어갈 값을 찾아 정렬하는 알고리즘입니다. 현재 위치에 저장 될 값의 크기가 작냐, 크냐에 따라 최소 선택 정렬(min-selection sort)와 최대 선택 정렬(max-slection sort)로 구분 됩니다.
최소 선택 정렬은 오름차순, 최대 선택 정렬은 내림차순으로 정렬됩니다.
기본 로직으로는
1. 정렬 되지 않은 인덱스의 맨 앞부터, 이를 포함한 그 이후의 배열 값 중 가장 작은 값을 찾습 니다.(시작 배열 위치는 인덱스[0])
2. 가장 작은 값을 찾으면, 현재 인덱스의 값과 바꾸어 줍니다.
3. 마지막 인덱스 까지 반복해 줍니다.
시간 복잡도는 O(n^2)입니다.
삽입 정렬(insertion sort)
삽입 정렬(insertion sort)이란 현재 위치에서, 그 이하의 배열들을 비교하여 자신이 들어갈 위치를 찾아, 그 위치에 삽입하는 배열 알고리즘입니다.
기본적인 롲직 순서는
1. 두 번째 인덱스에서 시작하며, 현재 인덱스는 별도의 변수로 저장해줍니다. 비교 인덱스를 현재 인덱스 -1로 합니다.
2. 별도 저장한 삽입을 위한 변수와ㅡ 비교 인덱스의 배열 값을 비교합니다.
3. 삽입 변수의 값이 더 작으면 현재 인덱스 값을 저장하고, 비교 인덱스를 -1하여 비교를 반복합 니다.
4. 만약 삽입 변수가 더 크면, 비교 인덱스 +1에 삽입 변수를 저장합니다.
정렬이 되어있을 경우 시간 복잡도는 O(n)이나, Big-O에 따라 최악의 경우를 따져 정렬 안됬을 경우인 O(n^2)가 됩니다.
퀵정렬(quick sort)
퀵 정렬(quick sort)이란 분할 정복(Divide and conquer)을 이용하여 정렬하는 알고리즘입니다.
pivot point라는 기준이 되는 값을 설정 하고, 이 값을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 옮기는 방식입니다.
이를 반복하여 분할된 배열의 크기가 1이되면 모두 정렬 된 것입니다.
퀵 정렬은 분할과 동시에 정렬을 진행하는 알고리즘이며, 시간 복잡도는 최선일 경우 O(nlog₂n)입니다만 Big-o에 따라 O(n^2)라고 할 수 있겠습니다.
선형탐색(Sequential Search)
input
def search_list(a,x):
n=len(a)
for i in range(0,n):
if x==a[i]:
return i
return -1
v=[13, 3, 33, 11, 17, 99, 38]
print(search_list(v,17))
print(search_list(v,33))
print(search_list(v,900))
print(v.index(38))
print(v.index(33))
try:
print(v.index(100))
except:
print('값이 없습니다.') output
4
2
-1
6
2
값이 없습니다.
이진 탐색(Binary Search)
input
def binary_search(i,x):
start = 0 #탐색범위의 시작 인덱스
end = len(i)-1 #탐색범위의 마지막 인덱스
cnt = 0
while start <= end:
mid=(start+end)//2 #중간 인덱스
if x==i[mid]: #값을 찾으면
return mid, i[mid], cnt #결과 리턴
elif x > i[mid]: # 더 큰 값이면
start = mid + 1 # 우측으로 탐색
else: # 더 작은값이면
end = mid - 1 #좌측으로 탐색
cnt += 1
return -1 #못찾으면 -1 리턴
serch = ['a','c','z','f','g']
serch.sort()
print(serch)
print(binary_search(serch,'g'))output
['a', 'c', 'f', 'g', 'z']
(3, 'g', 1)
버블정렬(bubble sort) 구현
input
# 기능 구현
def bubble_sort(x):
for i in range(0,len(x)):
for j in range(i+1, len(x)):
if x[i]>x[j]:
x[i],x[j]=x[j],x[i]
print(x)
return x
bs=[2,4,1,5,3]
print(bubble_sort(bs))
output
[2, 4, 1, 5, 3][1, 4, 2, 5, 3]
[1, 4, 2, 5, 3][1, 4, 2, 5, 3]
[1, 2, 4, 5, 3][1, 2, 4, 5, 3]
[1, 2, 4, 5, 3][1, 2, 4, 5, 3]
[1, 2, 3, 5, 4][1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]
함수 안에 print를 사용하여 인덱스[0]부터 정렬되는 것을 확인 할 수 있습니다.
선택정렬(selection sort) 구현
input
def sel_sort(a):
n=len(a)
for i in range(0,n-1):
min_idx=i #최소값의 위치
for j in range(i+1,n):
if a[j]<a[min_idx]:
min_idx=j
#print(i,j,a)
a[i],a[min_idx]=a[min_idx],a[i] #선택한 값을 i 위치에 저장
#print(i,j,a)
ss=[2,4,1,5,3]
sel_sort(ss)
print(ss) output
[1, 2, 3, 4, 5]
주석처리 하였습니다만 어떤 식으로 구현되는지 알고 싶으시면 주석처리된 print를 사용하시면 됩니다.
삽입 정렬(insertion sort)
input
def ins_sort(a):
n=len(a)
for i in range(1,n):
key=a[i] #삽입할 값
j=i-1
while j>=0 and a[j]>key:
a[j+1]=a[j]
j-=1
a[j+1]=key #삽입
#print(a)
ins=[5,1,3,2,4]
ins_sort(ins)
print(ins) output
[1, 2, 3, 4, 5]
input
def quicksort(array):
if len(array)<2:
return array
else:
pivot=array[0] #첫번째값 pivot 중심축
less=[i for i in array[1:] if i<=pivot] #기준보다 작은값들
greater=[i for i in array[1:] if i>pivot] #기준보다 큰값들
return quicksort(less)+[pivot]+quicksort(greater)
quicksort([-13,-17,3,13,33,17,11,28,]) output
[-17, -13, 3, 11, 13, 17, 28, 33]
오늘은 탐색과 정렬 알고리즘을 알아 보았습니다. 해당 알고리즘은 많은 사용과 코딩테스트에 이용가능 하기 때문에 여러 종류를 알아두면 좋을거 같다고 생각하였습니다. 오늘도 고생하셨고
😁 power through to the end 😁
