[정렬] 선택 정렬(Selection Sort)

- 기준에 가장 적합한 데이터를 선택해 (정렬된 데이터 제외) 맨 앞의 데이터와 교환하는 것을 반복
- 원시적인 방법, 비효율적임

 

시간 복잡도 : 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] #스와이프

 

 

---

정렬 전체가긔

이것이 코딩 테스트다 - 나동빈
정리하긔