선택 정렬

🌱 선택 정렬 (Selection Sort)

대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법

• 구현 방법이 복잡
• 시간 복잡도 O(n^2) (효율적이지 않아 코딩 테스트에서 많이 사용하지 않음)
  
  
  

🌱 선택 정렬의 핵심 이론

최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap 하는 것이 선택 정렬의 핵심

42, 32, 24, 60, 15 (최솟값 15와 swap) ▶ 15, 32, 24, 60, 42

15, 32, 24, 60, 42 (최솟값 24와 swap) ▶ 15, 24, 32, 60, 42

15, 24, 32, 60, 42 (최솟값 32와 swap) ▶ 15, 24, 32, 60, 42

15, 24, 32, 60, 42 (최솟값 42와 swap) ▶ 15, 24, 32, 42, 60

🌱 선택 정렬 과정

1. 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다.
2. 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap 한다.
3. 가장 앞에 있는 데이터의 위치를 변경해 (index++) 남은 정렬 부분의 범위를 축소한다.
4. 전체 데이터 크기만큼 index가 커질 때까지, 즉 남은 정렬 부분이 없을 때까지 반복한다.