선택 정렬(Selection Sort)이란?
선택 정렬은 루프가 반복될 때마다 배열에서 최솟값을 찾아내고, 그 값을 현재 위치의 요소와 교환(swap)하는 방식으로 동작하는 정렬 알고리즘입니다. 이 과정을 배열 전체가 정렬될 때까지 반복하면 오름차순으로 정렬된 결과를 얻을 수 있습니다.
선택 정렬은 구현이 매우 간단하고 직관적이어서 정렬 알고리즘을 처음 배울 때 자주 활용되며, 시간 복잡도는 데이터 개수와 관계없이 항상 O(n²)입니다.
C# 선택 정렬 예제 코드
다음은 C#으로 작성한 선택 정렬 프로그램의 전체 코드입니다.
using System;
public class Example {
static void Main(string[] args) {
int[] arr = new int[10] { 56, 1, 99, 67, 89, 23, 44, 12, 78, 34 };
int n = 10;
Console.WriteLine("Selection sort");
Console.Write("Initial array is: ");
for (int i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
int temp, smallest;
for (int i = 0; i < n - 1; i++) {
smallest = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[smallest]) {
smallest = j;
}
}
temp = arr[smallest];
arr[smallest] = arr[i];
arr[i] = temp;
}
Console.WriteLine();
Console.Write("Sorted array is: ");
for (int i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
}
}
실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
Selection sort Initial array is: 56 1 99 67 89 23 44 12 78 34 Sorted array is: 1 12 23 34 44 56 67 78 89 99
코드 단계별 설명
1. 배열 초기화 및 초기 상태 출력
먼저 정렬할 정수형 배열을 선언하고 초기화한 뒤, for 루프를 사용하여 배열의 초기 상태를 콘솔에 출력합니다.
int[] arr = new int[10] { 56, 1, 99, 67, 89, 23, 44, 12, 78, 34 };
int n = 10;
Console.WriteLine("Selection sort");
Console.Write("Initial array is: ");
for (int i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
2. 중첩 for 루프를 이용한 정렬 과정
실제 정렬은 중첩 for 루프를 통해 수행됩니다. 바깥쪽 루프가 한 번 실행될 때마다 현재 위치(i)부터 배열 끝까지의 범위에서 가장 작은 값을 찾아 현재 요소와 교환합니다. 내부 루프는 나머지 요소들을 하나씩 비교하며 최솟값의 인덱스(smallest)를 갱신하고, 내부 루프가 종료되면 해당 최솟값을 현재 위치의 값과 맞바꿉니다. 이 과정을 배열이 완전히 정렬될 때까지 반복합니다.
for (int i = 0; i < n - 1; i++) {
smallest = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[smallest]) {
smallest = j;
}
}
temp = arr[smallest];
arr[smallest] = arr[i];
arr[i] = temp;
}
3. 정렬된 배열 출력
정렬이 모두 완료되면 마지막으로 for 루프를 사용해 정렬된 배열을 콘솔에 출력합니다.
Console.Write("Sorted array is: ");
for (int i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
마무리
선택 정렬은 구조가 단순하여 이해하기 쉽다는 장점이 있지만, 모든 경우에서 O(n²)의 시간 복잡도를 가지므로 데이터 양이 많은 경우에는 퀵 정렬(Quick Sort)이나 병합 정렬(Merge Sort)처럼 더 효율적인 알고리즘을 사용하는 것이 좋습니다. 반면 교환 횟수가 적다는 특징이 있어, 교환 비용이 큰 환경에서는 유용하게 활용될 수 있습니다.