선택 정렬 (Selection Sort)
목차
주어진 데이터에서 최소값을 찾은 후 그 값을 해당 인덱스와 스왑. 0번부터 차례대로 최소값이 정해지는 방식.
구현
def selection_sort(data):
for index in range(len(data) - 1):
lowest_idx = index
for selection in range(index + 1, len(data)):
if data[lowest_idx] > data[selection]:
lowest_idx = selection
data[lowest_idx], data[index] = data[index], data[lowest_idx]
return data시간 복잡도
| 경우 | 복잡도 |
|---|---|
| 일반 | O(n²) |
| 최악 | n*(n-1)/2 |
| 완전 정렬 상태 | O(n) |