학교강의/컴퓨터 알고리즘

선택 정렬 알고리즘

Fel.Forest 2023. 9. 15. 11:30

개념 : 오른쪽 리스트에서 가장 작은 숫자를 선택하여 왼쪽 리스트의 맨 뒤로 이동하는 작업을 반복

예시 :

정렬 된 리스트 정렬 전 리스트 가장 작은 값 찾는 인덱스 순서 
[ ] [ 9, 7, 1, 5, 3 ] min = 0 -> 1-> 2
[ 1 ] [ 9, 7, 5, 3 ] min = 0 -> 1 -> 2 -> 3
[ 1, 3 ] [ 9, 7, 5 ] min = 0 -> 1 -> 2
[ 1, 3, 5 ]  [ 9, 7 ] min = 0 -> 1
[ 1, 3, 5, 7 ] [ 9 ]  min = 0
[ 1, 3, 5, 7 ,9 ] [ ]  

위 방법은 별로임 리스트를 하나 더 사용하기 때문에 메모리가 낭비된다고 보면 된다

그러면 어떻게 해야 하나 -> 그냥 자리 교환만 하면 된다

리스트 원하는 자리 인덱스 가장 작은 값 찾는 인덱스 순서
[ 9, 7, 1, 5, 3 ] 0 2
[ 1 ,9, 7, 5, 3 ] 1 4
[ 1, 3, 9, 7, 5 ] 2 4
[ 1, 3, 5, 9, 7 ] 3 4
[ 1, 3, 5, 7, 9 ] 4 4
[ 1, 3, 5, 7, 9 ]    

선택정렬 특징 데이터에 민감하지 않음