Selection sort
선택 정렬
가장 작은 값을 찾아 앞자리를 채워요
배열을 오름차순으로 정렬해요
정렬된 원소0
이번에 채울 위치0
최솟값 후보—
현재 위치비교 대상확인한 값
예제 코드
C++
<vector> <utility>std::vector<int> selection_sort(std::vector<int> a) { for (int i = 0; i + 1 < static_cast<int>(a.size()); ++i) { int smallest = i; for (int j = i + 1; j < static_cast<int>(a.size()); ++j) { if (a[j] < a[smallest]) smallest = j; } std::swap(a[i], a[smallest]); } return a;}Python
def selection_sort(a): a = a.copy() for i in range(len(a) - 1): smallest = i for j in range(i + 1, len(a)): if a[j] < a[smallest]: smallest = j a[i], a[smallest] = a[smallest], a[i] return a시작하기
왼쪽부터 자리를 채워요
남은 원소에서 가장 작은 값을 찾아 맨 앞에 놓아요. 같은 과정을 반복해요.
사용 조건
정렬이 어떤 비교와 교환으로 이루어지는지 익히기 좋아요. 큰 입력에서 빠른 정렬이 필요하면 더 효율적인 정렬을 선택해요.
먼저 알아두면 좋아요
배열과 중첩 반복문을 알고 시작해요. 값의 교환은 두 위치를 서로 바꾸는 동작이에요.
동작 원리
아직 정렬되지 않은 구간의 첫 값을 최솟값 후보로 잡아요. 나머지 값을 비교하며 더 작은 값의 위치를 기억해요.
최솟값을 그 구간의 맨 앞과 교환해요. 왼쪽에 확정된 구간이 한 칸씩 늘어나고, 마지막 원소는 자연스럽게 남은 자리에 놓여요.
- 시간
- O(n²) · 남은 원소를 매번 다시 비교해요
- 추가 공간
- 교환 O(1) · 입력 보존용 복사본은 O(n)
주의할 점
- 최솟값 자체가 아니라 위치를 기억해야 올바른 두 원소를 교환할 수 있어요.
- 최솟값 후보는 매 바깥 반복마다 새로 정해요. 이미 정렬된 구간은 다시 비교하지 않아요.
작성·운영 xhae123