선택 정렬(Selection Sort) - 정의 / 예시 코드

 

선택 정렬(Selection Sort)은 간단하면서도 직관적인 정렬 알고리즘입니다. 주어진 배열에서 가장 작은(또는 가장 큰) 원소를 선택하여 정렬 순서에 맞게 앞으로 이동시키는 방식으로 동작합니다.

 

아래는 선택 정렬의 동작 과정을 단계별로 설명한 것입니다.

 

1. 주어진 배열에서 가장 작은(또는 가장 큰) 원소를 찾습니다.

 

2. 해당 원소를 정렬 순서에 맞게 배열의 첫 번째 위치(또는 마지막 위치)와 교환합니다.

 

3. 정렬된 부분과 정렬되지 않은 부분으로 배열을 나눕니다.

 

4. 정렬되지 않은 부분에서 다음으로 작은(또는 큰) 원소를 선택하여 해당 위치에 삽입합니다.

 

5. 위의 과정을 정렬되지 않은 부분의 원소가 모두 정렬될 때까지 반복합니다.

 

반응형

 

아래는 C++로 구현된 선택 정렬의 예시 코드입니다.

 

 

위의 예시 코드를 실행하면, 배열 {64, 25, 12, 22, 11}가 오름차순으로 정렬되어 {11, 12, 22, 25, 64}가 출력됩니다.

선택 정렬은 배열의 크기가 작을 때 유용하며, 시간 복잡도는 항상 O(n^2)입니다. 비교 연산의 수가 배열의 크기의 제곱에 비례하기 때문에 큰 배열에 대해서는 비효율적일 수 있습니다.