알고리즘 이론 - 선택 정렬
선택 정렬(select sort)
- 선택 정렬은 리스트를 순회하며 최솟값을 찾아 해당 인덱스의 값을 현재 인덱스의 값과 바꿔주는 정렬이다.
위 사진을 보면 순서대로 현재 수와 다른 수들을 전부 비교해서 자리를 바꿔주는 것을 확인할 수 있다. 알기 쉽도록 아래의 코드를 확인하자.
#선택 정렬
def select_sort(list_num):
for i in range(0, len(list_num) - 1): # 마지막 index는 비교할 대상이 없음.
min_idx = i # 탐색 과정에서 가장 작은 값을 찾아 현재 인덱스와 바꿔줄 변수를 초기화.
for j in range(i + 1, len(list_num)): #두 번째 인덱스부터 끝까지 탐색.
if list_num[j] < list_num[min_idx]: # 현재 인덱스의 값과 다음 인덱스들인 list_num[j]의 값을 비교해 최소값을 찾아 min_idx에 저장한다.
min_idx = j
list_num[i], list_num[min_idx] = list_num[min_idx], list_num[i] # 순회 후에 가장 작은 인덱스의 값과 현재 인덱스를 바꿔준다.
return list_num
print(select_sort([2, 4, 5, 1, 3, 4, 7, 30]))
*선택 정렬은 순회를 하지만 매번 리스트안의 위치를 바꾸진 않아 버블정렬보다는 효율이 좋은 편이지만 이중 반복문을 순회하므로 시간 복잡도는 O(N^2)이다.
Author And Source
이 문제에 관하여(알고리즘 이론 - 선택 정렬), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@code_alpaca/알고리즘-이론-선택-정렬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)