Py) 선택정렬 Selection Sort

• 제자리정렬(in-place sorting): 입력배열 외에는 다른 추가 메모리를 요구하지 않는 정렬방법
• 안정정렬
• 성능분석: 비교횟수 - 두개의 for 루프 중 외부루프 n-1번, 내부루프 0 ~ n-2까지 변하는 i에 대해 (n-1)-i번 반복. 
  • (n-1)+(n-2)+...+1=n(n-1)/2 = O(n^2)

 

알고리즘

1. 첫번째 인덱스를 최소값 인덱스로 설정한다
2. 그 다음 인덱스부터 마지막 인덱스의 값(array[j])과 최소값 인덱스의 값을 비교한다
3. 만약 array[j]의 값이 최소값 인덱스보다 작다면 최소값 인덱스를 변경한다.
4. swap을 통해 자리를 바꿔준다

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 #최소값 변경
    #swap
    array[i], array[min_index] = array[min_index], array[i]

print(array)