선택 정렬

📢

• 여기서 소개하는 정렬은 오름차순정렬을 기준으로 합니다.
• n개의 원소를 저장하는 배열A를 A[0 ⋯ n - 1]라고 표현하겠습니다.

개념

일반적으로 선택 정렬은 A[0 ⋯ n - 1]에서 가장 큰 요소를 찾아 이 요소와 배열의 끝자리에 있는 요소랑 자리를 바꾸는 방식으로 동작하는 알고리즘입니다. 매 번 배열을 돌 때마다 맨 끝으로 옮겨진 요소는 자기 자리(정렬된 위치)를 찾게 되고, 이를 반복하면 배열이 정렬됩니다.

선택 정렬의 첫 번째 패스는 요소를 n-1번, 두 번째 패스는 n-2번, 세 번째는 n-3번, … 순회하여 마지막 패스는 1번 순회하게 됩니다. 따라서 선택 정렬의 총 순환 횟수는 (n-1)+(n-2)+…+1번 이므로 시간 복잡도는 $O(n^2)$이 됩니다.

구현 코드

구현 코드 보러가기