탐색은 : 여러 개의 자료 중에서 원하는 것을 찾아내는 것
정렬은 : 주어진 자료를 순서에 맞춰 나열하는 것
07. 순차 탐색
주어진 리스트에 특정한 값이 있는지 찾아 그 위치를 돌려주는 알고리즘
sequential search
1. 순차 탐색으로 특정 값의 위치 찾기
def search_list(a, x):
n = len(a)
for i in range(0,n):
if x == a[i]:
return i
return -1
2. 알고리즘 분석
계산 복잡도 O(n)
08. 선택 정렬
1. 선택 정렬로 줄 세우기
2. 쉽게 설명한 선택 알고리즘
def find_min_idx(a):
n = len(a)
min_idx = 0
for i in range(1, n):
if a[i] < a[min_idx]:
min_idx = i
return min_idx
def sel_sort(a):
result = []
while a:
min_idx = find_min_idx(a)
value = a.pop(min_idx)
result.append(value)
return result
3. 일반적인 선택 알고리즘
def sel_sort(a):
n = len(a)
for i in range(0,n-1):
min_idx = i
for j in range(0,n-1):
if a[j] < a[min_idx]:
min_idx = j
a[i], a[min_idx] = a[min_idx], a[i]
4. 알고리즘 분석
O(n^2)
09. 삽입 정렬
리스트 안의 자료를 작은 수 부터 큰 순서로 배열하는 정렬 알고리즘
1. 삽입 정렬로 줄 세우기
2. 쉽게 설명한 삽입 정렬 알고리즘
def find_ins_idx(r, v):
for i in range(0, len(r)):
if v < r[i] :
return i
return len(r)
def ins_sort(a):
result = []
while a:
value = a.pop(a)
ins_idx = find_ins_idx(result , value)
result.insert(ins_idx , value)
return result
3. 일반 적인 삽입 정렬
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
4. 알고리즘 분석
O(n^2)
문제 10 : 병합 정렬
리스트 안의 자료를 작은 수부터 큰 수 순서로 배열하는 정렬 알고리즘을 만들어 보세요.
1. 병합 정렬로 줄 세우기
2. 쉽게 설명한 병합 정렬 알고리즘
def merge_sort(a):
n = len(a)
if n <= 1:
return a
mid = n //2
g1 = merge_sort(a[:mid])
g2 = merge_sort(a[mid:])
result = []
while g1 and g2:
if g1[0] < g2[0]:
result.append(g1.pop(0))
else:
result.append(g2.pop(0))
while g1:
result.append(g1.pop(0))
while g2:
result.append(g2.pop(0))
return result
3. 병합 정렬에서의 재귀 호출
4. 일반적인 병합 정렬 알고리즘
def merge_sort(a):
n = len(a)
if n <= 1:
return
mid = n //2
g1 = a[:mid]
g2 = a[mid:]
merge_sort(g1)
merge_sort(g2 )
i1 = 0
i2 = 0
ia = 0
while i1< len(g1) and i2< len(g2):
if g1[i1] < g2[i2]:
a[ia] = g1[i1]
i1 += 1
ia += 1
else:
a[ia] = g2[i2]
i2 += 1
ia += 1
while i1< len(g1):
a[ia] = g1[i1]
i1 += 1
ia += 1
while i2< len(g2):
a[ia] = g1[i2]
i2 += 1
ia += 1
5. 알고리즘 분석
문제 11. 퀵정렬
그룹을 둘로 나눠 재귀 호출하는 방식
def quick_sort(a):
n = len(a)
if n <=1:
return a
pivot = a[-1]
g1 = []
g2 = []
for i in range(0,n-1):
if a[i] < pivot:
g1.append(a[i])
else:
g2.append(a[i])
return quick_sort(g1)+[pivot] + quick_sort(g2)
def quick_sort_sub(a, start, end):
if end - start <= 0:
return
pivot = a[end]
i = start
for j in range(start, end):
if a[j] <= pivot:
a[i], a[j] = a[j] , a[i]
i+=1
a[i],a[end] = a[end],a[i]
quick_sort_sub(a, start, i-1)
quick_sort_sub(a, i+1, end)
def quick_sort(a):
quick_sort_sub(a, 0, len(a)-1)
문제 12. 이분 탐색
둘로 나눈다 탐색할 자료를 둘로 나누어 찾는 값이 있을 법한 곳만 탐색하기 때문에 자료를 하나하나 찾아야 하는 순간 탐색보다 원하는 자료를 훨씬 빨리 찾을 수 있습니다.
def binary_search(a, x):
start = 0
end = len(a) -1
while start <= end:
mid = (start+end)//2
if x == a[mid]:
return mid
elif x > a[mid]:
start = mid +1
else:
end = mid-1
return -1
출처 : 모두의 알고리즘 with 파이썬
'책 > 모두의 알고리즘 with 파이썬' 카테고리의 다른 글
04. 자료구조,05. 응용문제 (0) | 2020.08.30 |
---|---|
00. 들어가는 글,첫째마당 알고리즘 기초,02. 재귀호출 (0) | 2020.08.22 |