Selection Sort

선택 정렬(Selection Sort)

---

선택 정렬은 정렬 순서에 맞게 하나씩 데이터를 선택해 옮기면서 정렬을 진행하는 알고리즘입니다. 정렬 순서상 가장 앞에 위치해야 하는 요소를 선택해 가장 왼쪽으로 이동시키고, 원래 그 자리에 있던 데이터를 빈 자리에 가져다 놓는 방식입니다.

즉, 배열에서 가장 작은(또는 가장 큰) 값을 찾아 첫 번째 요소와 교환한 후, 그 다음 작은 값을 두 번째 요소와 교환하는 방식으로 반복합니다.

구현

---

#include <stdio.h>

void SelSort(int arr[], int n) {
   int i, j;
   int maxIdx;  // 가장 작은 값을 가리킬 인덱스
   int temp;    // 값을 임시로 저장할 변수

   for (i = 0; i < n - 1; i++) {
      maxIdx = i;

      for (j = i + 1; j < n; j++) {
         if (arr[j] < arr[maxIdx]) {  // 내림차순은 arr[j] > arr[maxIdx]
            maxIdx = j;
         }
      }

      // 선택한 최소값과 현재 i 위치의 값 교환
      temp = arr[i];
      arr[i] = arr[maxIdx];
      arr[maxIdx] = temp;
   }
}

int main(void) {
   int arr[4] = { 3, 4, 2, 1 };
   
   // 배열 정렬
   SelSort(arr, sizeof(arr) / sizeof(int));

   // 결과 출력
   for (int i = 0; i < 4; i++) {
      printf("%d ", arr[i]);
   }

   printf("\n");
   return 0;
}

성능 평가

선택 정렬의 성능을 분석해 보면, 반복문의 동작을 확인할 수 있습니다.

   for (i = 0; i < n - 1; i++) {
      maxIdx = i;

      for (j = i + 1; j < n; j++) {
         if (arr[j] < arr[maxIdx]) {
            maxIdx = j;
         }
// 이하 생략

i가 0일 때, j는 1부터 $n-1$까지 증가하면서 배열을 탐색합니다. 이때 선택 정렬의 비교 연산은 $n-1$회 수행됩니다. i가 1일 때는 j가 2부터 $n-1$까지 탐색하므로, $n-2$회의 연산이 수행됩니다. 이를 반복하여 총 비교 횟수는 다음과 같습니다:

따라서 선택 정렬의 시간 복잡도는 버블 정렬과 마찬가지로 $O(n^2)$입니다. 이는 데이터의 크기에 따라 연산 시간이 제곱에 비례하여 증가하는 것을 의미합니다.

선택 정렬의 장단점

---

장점 :

• 선택 정렬은 구현이 매우 간단하고, 추가적인 메모리가 필요하지 않습니다. 정렬을 진행하면서 데이터를 교환하는 방식이므로 in-place 정렬입니다.

• 데이터의 크기가 작거나 거의 정렬된 경우, 상대적으로 간단하게 사용할 수 있습니다.

단점:

• 선택 정렬의 주요 단점은 시간 복잡도입니다. 비교 횟수가 $O(n^2)$으로, 대량의 데이터나 정렬되지 않은 데이터를 다룰 때는 비효율적입니다.

• 다른 효율적인 정렬 알고리즘(예: 퀵 정렬, 병합 정렬)과 비교했을 때, 선택 정렬은 대규모 데이터 세트에서는 성능이 떨어집니다.

결론

---

선택 정렬은 그 단순한 구현과 이해하기 쉬운 개념 덕분에 정렬 알고리즘의 기초를 배우는 데 자주 사용됩니다. 그러나 시간 복잡도가 $O(n^2)$로 비효율적이기 때문에, 실제로 사용되는 경우는 많지 않습니다. 작은 데이터 세트에서는 간단하고 효과적일 수 있지만, 대규모 데이터를 다루는 상황에서는 퀵 정렬이나 병합 정렬과 같은 더 효율적인 알고리즘을 사용하는 것이 좋습니다.