주어진 자료들 중 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식으로 셀렉션 알고리즘을 적용한 것
# 오름차순으로 정렬
lst = [64, 25, 10, 22, 11]
lst = [64, 25, 10, 22, 11]
min_val = 0
for i in range(len(lst)-1):
min_val = i
for j in range(i, len(lst)):
if lst[j] < lst[min_val]:
min_val = j # 최소값의 인덱스를 찾는다
lst[i], lst[min_val] = lst[min_val], lst[i] # 위치 교환하기
저장되어 있는 자료로부터 k번째로 크거나, 작은 원소를 찾는 방법
=> 최소값, 최대값 혹은 중간값을 찾는 알고리즘
k번째로 작은 원소 찾기
- 1번부터 k번째까지 작은 원소들을 찾아 배열의 앞쪽으로 이동시키고, 배열의 k번째를 반환한다.
- k가 비교적 작을 때 유용하며 O(kn)의 수행시간을 필요로 한다.
def select(arr, k):
for i in range(0, k):
minIndex = i
for j in range(i+1, len(arr)):
if arr[minIndex] > arr[j]:
minIdex = j
arr[i], arr[minIdex] = arr[minIdex], arr[i]
return arr[k-1]