선택정렬
선택 정렬은 이름에 맞게 현재 위치에 들어갈 값을 찾아 정렬하는 배열입니다. 현재 위치에 저장 될 값의 크기가 작냐, 크냐에 따라 최소 선택 정렬과 최대 선택 정렬로 구분 할 수 있습니다.최소 선택 정렬은 오름차순으로 정렬될 것이고, 최대 선택 정렬은 내림차순으로 정렬될 것입니다.
기본 로직은 아래와 같습니다.
- 정렬되지 않은 인데스의 맨 앞에서 부터, 이를 포함한 그 이후의 배열값 중 가장 작은 값을 찾아감(정렬되지 않은 인덱스의 맨 앞은, 초기 입력에서는 배열의 시작위치일 것입니다.)
- 가장 작은 값을 찾으면, 그 값을 현재 인덱스의 값과 바꿔줌
- 다음 인덱스에서 위 과정을 반복해줌
이해를 돕기 위해 이미 정렬이 끝난 부분과 앞으로 처리될 대상 범위 사이에 세로선( | )을 넣어 구분하여 설명하겠습니다.
| 2 4 5 1 3 시작, 전체리스트인 2, 4, 5, 1, 3을 대상으로 최솟값을 찾습니다.
| 1 4 5 2 3 // 최솟값 1을 대상의 가장 왼쪽 값인 2와 바꿉니다.
1 | 4 5 2 3 // 1을 대상에서 제외하고 4, 5, 2, 3에서 최솟값을 찾습니다.
1 | 2 5 4 3 // 4, 5, 2, 3 중 최솟값인 2를 4와 바꿉니다.
1 2 | 5 4 3 // 2를 대상에서 제외하고 5, 4, 3에서 최솟값을 찾습니다.
1 2 | 3 4 5 // 5, 4, 3중 최솟값인 3을 5와 바꿉니다.
1 2 3 | 4 5 // 3을 대상에서 제외하고 4, 5에서 최솟값을 찾습니다.
1 2 3 | 4 5 // 최솟값 4를 4와 바꿉니다.(변화없음)
1 2 3 4 | 5 // 4를 대상에서 제외합니다. 자료가 5하나만 남았으므로 종료합니다.
1 2 3 4 5 | // 최종결과입니다.
