선택 정렬(selection sort) 란?

선택 정렬의 원리 

선택 정렬(selection sort)은 가장 이해하기가 쉬운 정렬 방법이다. 

 

 

출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

 

 

선택 정렬은 다른 추가 메모리를 요구하지 않는 정렬 방법인 제자리 정렬(in-place-sorting)을 이용한다. 

 

• 초기 배열에서 최소값을 찾는다.
• 이 최소값을 배열의 첫번째 요소와 교환한다.
• 그리고 첫번째 요소를 제외한 나머지 요소들 중에서 가장 작은 값을 선택하고 이를 두번째 요소와 교환한다.
• 위의 절차를 (배열원소-1)만큼 반복하면 추가적인 배열을 사용하지 않고 정렬 가능하다.

 

 

이제 자바를 이용해서 선택 정렬을 구현해보자. 

 

 

 

선택 정렬의 분석

선택 정렬의 성능 분석을 위하여 비교 횟수와 이동 횟수를 따로 구하여 보자. 먼저 비교 횟수를 구하기 위하여 두개의 for 루프의 실행 횟수를 계산해보자. 

 

외부루프는 n-1번 실행될 것이며 내부루프는 0에서 n-2까지 변수는 i에 대하여 (n-1)-i번 반복될 것이다. 

그렇기 때문에 비교가 내부 루프 안에서 이루어지므로 전체 비교횟수는 다음과 같다.

(i는 0에서 n-2 로 변한다. 따라서 내부 루프는 (n-1) x (n-1-i) 번 돌게 된다)

 

(n-1) + (n-2) + ... +1 = n(n-1)/2 = O(n*n) 

 

이 된다. if 문이 2번 째 for문 안에서 한번 씩 실행이 되므로 2번 째 for문이 돌아가는 횟 수 만큼 비교를 한다.

교환 횟수는 외부 루프의 실행 횟수와 같으며 한번 교환하기 위하여 3번의 이동이 필요하다(Swap) 

따라서 3(n-1)이 된다. 

 

 

선택 정렬의 장단점

• 장점 

  • 자료 이동 횟수가 미리 결정된다는 점이다. 
  • 일반적으로 비교 연산1개가 이동 연산 3개보다 시간이 적게 걸리므로 효과적이다.

• 단점

  • 이동 횟수는 3(n-1)이면 상당히 큰 편이다. 
  • 안정성을 만족하지 않는다.
  • 자료가 정렬된 경우에는 불필요하게 자기 자신과의 이동을 하게 된다.

 

여기서 안정성이라는건 어떤말 일까? 

B b a c 가 있다고 가정해보자. B = b 이다 그냥 같은 숫자라고 생각하면 된다.  

이것을 정렬을 해보면  a b B c 가 된다.  이렇게 처음에는 B가 b 보다 앞에 있었는데 정렬 후에는 b 가 B보다 앞에 있는 경우를 불안정하다고 표현한다. (B와 b 는 그냥 같지만 구분을 위해서 대문자, 소문자로 해놨음)

이렇게 순서가 유지되지 않는 경우를 불안정 정렬이라하고 선택 정렬은 불안정 정렬이 되는 것이다.

 

https://mygumi.tistory.com/94

선택 정렬이 불안정 정렬인 이유 :: 마이구미

위의 글을 보고 참고를 하였다. 

 

 

출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

 

앞으로 공부할 정렬인데 시간 복잡도에 대해서 계속 보고자 가져오게 되었다. 

선택정렬은 언제나 시간복잡도 n*n 을 가진다는 점을 기억하자.