선택 정렬 - Java

선택 정렬 개념

• 제자리 정렬 (in-place sorting)이다. 입력 배열 외에는 추가 메모리를 요구하지 않는 정렬이다.
• 정렬된 해당 요소가 넣어질 위치가 정해져 있다.
• 자료 이동 횟수가 미리 결정된다. →  n-2번

 

구체적인 설명

• 선택 정렬이란 첫 번째 위치부터 차례대로 정렬이 안된 요소 중 가장 작은 것(큰 것)을 선택하여 위치를 교환하여 점점 정렬을 완료해나가는 기법이다.
• 첫번째 루프일 때 첫번 째 요소를 두번 째 요소부터 마지막 요소까지 비교하여 가장 작은 값을 찾으면 해당 요소와 교환한다. 두번 째 루프일 때 두번 째 자료를 세번 째 요소 부터 마지막 요소까지 비교하여 가장 작은 요소를 찾으면 해당 요소와 교환한다. 이렇게 n-1 요소까지 반복한다.

 

시간 복잡도

비교 횟수

• (n-1) + (n-2) + … 2 + 1 = O(n^2)

이동 횟수

• 3(n-1) ⇒ 매우 큰 편

 

특징

장점

• 제자리 정렬이다
• 자료 이동 횟수가 미리 결정된다.

단점

• 안정성을 만족하지 않는다.