선택 정렬(Selection Sort)

선택정렬은 정렬되지 않은 값들을 순차적으로 탐색 해 가면서 정렬하는 방법으로 아래 순서로 된다.

 

1. 배열의 가장 첫번째 값을 선택한다.

2. 선택된 다음 값부터 가장 작은 값을 찾아낸다.

3. 그 값과 선택된 값을 바꿔준다.

4. 정렬이 된 다음 값부터 모든 값이 정렬될 때 까지 반복한다.

 

방법이 단순한 만큼 구현하기도 쉽지만, 시간복잡도는(알고리즘을 완료하는데 걸리는 시간) 배열의 크기 * (n^2)로 오래걸린다.

코드로 구현 시 이렇게 되며, 여기에

9, 8, 7, 6, 5, 4, 3, 2, 1, 0으로 이루어진 배열을 넣으면

이렇게 출력이 된다.

간단하게 0번 인덱스만 진행 순서를 보자.

 

1. 0번 인덱스(9)의 값이 선택된다.

2. 1번 인덱스(8)와 비교한다.

3. 1번 인덱스가 값이 더 작기때문에 1번을 저장한다.

4. 마지막 인덱스까지 2, 3번을 반복한다.

5. 가장 작은 값인 9번 인덱스(0)와 0번 인덱스를 바꿔준다.

6. 배열 크기보다 한개 작은 횟수(자기 자신과 다음값부터 비교하기 때문에 마지막값은 비교 할 필요가 없다.)만큼 1~5번을 반복한다.

 

처음에도 언급했지만, 정말 단순하면서도 비효율적인 정렬 알고리즘이다.