Selection Sort

해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘

최소값을 찾고 위치 값과 교환. 나머지도 같은 방법으로 교체.

A = [64, 25, 12, 22, 11]
for i in range(len(A)):
	min_idx = i
    for j in range(i+1, len(A)):
    	if A[min_idx] > A[j]:
        	min_idx = j
    A[i], A[min_idx] = A[min_idx], A[i]

시간복잡도

O(n^2)

공간복잡도

O(n), swap을 주어진 배열 안에서 수행

장점

단순한 알고리즘

제자리 정렬(in-place sorting)

정렬을 위한 비교횟수는 많으나 bubble sort에 비해 실제 교환횟수는 적음

단점

비효율적. 시간 복잡도 O(n^2)

불안정 정렬(unstable sort)

References

https://github.com/GimunLee/tech-refrigerator/blob/master/Algorithm/%EC%84%A0%ED%83%9D%20%EC%A0%95%EB%A0%AC%20(Selection%20Sort).md#%EC%84%A0%ED%83%9D-%EC%A0%95%EB%A0%AC-selection-sort

https://www.geeksforgeeks.org/selection-sort/

Selection Sort Algorithm – Data Structure and Algorithm Tutorials - GeeksforGeeks