[알고리즘] 선택정렬

n개의 데이터를 정렬할 때 총 회전 수는 n-1개

(마지막 데이터는 나머지가 다 정리된 뒤 남은 값이기 때문에 정렬할 필요가 없다)

 

다음은 5개의 데이터를 오름차순으로 정리하는 문제입니다.

 

5개의 데이터를 서로 비교해서 작은 값부터 왼쪽으로 보내 정렬하는 건데요.

 

 

이때 1회전 때 (1)번지의 값을 (2), (3), (4), (5) 번지의 값들과 비교해

 

가장 작은 값을 찾아 (1)번지에 넣어야 합니다.

 

비교가 끝나면 가장 작은 값이 (1)번지에 들어가면서 1회전이 끝나게 됩니다.

 

 

4회전까지 진행하고 나면 이런 형태가 되는데요.

 

이때 5회전을 하지 않고 종료됩니다.

 

남은 값이 하나일 때는 이미 다른 값들과 비교가 끝난 상태이기 때문이죠.

 

 

이때 비교하려는 두 값을 i, j 변수에 넣고 비교한다면 이런 형태가 됩니다.

 

 

자세히 보면 회전마다 동일한 공통점이 있는데요.

 

j의 시작값이 i에서 +1 되는 걸 알 수 있습니다.

 

반복값을 표현하면

 

i = 1, 4, 1

 

j = i+1, 5, 1

 

이 됩니다.

 

위와 같은 경우는 5개의 데이터로 한정된 경우지만

 

그렇지 않고 n값으로 설정됐을 때는 결국

 

i = 1, n-1, 1

 

j = i+1, n, 1

 

이 됩니다.

 

이를 순서도로 나타내면 이와 같습니다.

 

 

A(i) > A(J) 가 YES여서 교환한다면 작은 값이 앞으로 보내지기 때문에 오름차순,

 

A(i) < A(J) 가 YES여서 교환한다면 큰 값이 앞으로 보내지기 때문에 내림차순이 되므로

 

부등호의 방향에 주의해야 합니다.

 

그 아래 T 변수는 교환로직을 사용하기 위한 임시변수입니다.

 

교환로직에 대한 정보는 아래 포스팅을 참고해주세요.

 

https://ho-ding.tistory.com/59

[알고리즘] ㄹ자 채우기