학/Algorithm
[정렬] 선택 정렬(Selection Sort)
이준늬
2023. 3. 4. 00:30
- 기준에 가장 적합한 데이터를 선택해 (정렬된 데이터 제외) 맨 앞의 데이터와 교환하는 것을 반복
- 원시적인 방법, 비효율적임
시간 복잡도 : O(N^2) ≒ (N^2 + N)/2 ≒ N! ≒ 연산 횟수
공간 복잡도: O(N)
연산 횟수: N + (N-1) + (N-2) + ... + 2
N개 확인, 정렬된 1개의 데이터를 제외하고 확인 ... 마지막 하나 남은 경우는 확인하지 않아도 됨
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(len(array)):
min_index = i
for j in range(i+1, len(array)):
if array[min_index] > array[j]:
min_index = j
array[i], array[min_index] = array[min_index], array[i] #스와이프