[Algorithm] 선택 정렬 (Selection Sort)

선택 정렬 (Selection Sort)

 선택 정렬은, 배열의 제일 앞에서부터 해당 자리에 들어갈 숫자를 선택하는 정렬이다. 들어갈 숫자를 결정하는 것은 배열 내의 모든 요소를 비교해 가장 작은 것을 선택한다. 다음 loop 부터는 이미 자리가 결정된 숫자는 비교하지 않고, 나머지 수들 중에 들어갈 것을 찾기를 반복한다.

 

즉, 1번째 loop에서는 배열의 첫 번째 자리에 들어갈 원소를 n개를 모두 비교해 선택하고,

2번째 loop에서는 이미 결정된 첫 번째 자리의 숫자를 제외한 나머지 n-1개를 비교해 두 번째 자리에 들어갈 숫자를 결정한다.

3번재 loop에서는 이미 결정된 1~2번째 자리의 숫자를 제외한 나머지 n-2개를 비교해 세 번째 자리에 들어갈 숫자를 결정하고,

모든 자리에 들어갈 숫자가 정해질 때까지 반복된다.

 

 

선택 정렬 (출처 : https://wonjayk.tistory.com/)

 

위 그림은 선택 정렬을 나타내는 그림이다.

이 그림에서는 한 단계 = 한 loop라고 보면 좋다.

한 단계마다 앞에서부터 자리의 숫자가 결정되며, 결정될 숫자는 나머지 배열에서 가장 작은 숫자를 선택하면 된다는 것이다.

 

선택 정렬 파이썬 코드

 

 

선택 정렬 자바 코드

 

 

 

선택 정렬 장단점

 

- 선택정렬의 장점

간단한 구현, 개발 시간을 줄일 수 있다.

 

- 선택정렬의 단점

데이터를 하나씩 비교하기 때문에 좋지 않은 시간 복잡도를 가졌다. (O(n^2))

정렬된 상태에서 새로운 데이터가 삽입되면 정렬 효율이 좋지 않다. (정렬이 되어있더라도, 이 상태를 고려하지 않고 가장 작은 원소를 찾으려 모은 원소를 비교할 것이므로.)