정렬 알고리즘 - 선택 정렬 (Selection sort)

 

선택 정렬(Selection Sort) 이란?

 

 

선택 정렬은 간단하지만 효율적인 정렬 알고리즘 중 하나입니다. 이 알고리즘은 주어진 리스트에서 가장 작은(또는 큰) 원소를 선택하여 리스트의 처음부터 차례대로 정렬되는 위치로 옮기는 과정을 반복합니다. 이 과정에서 선택 정렬은 정렬된 부분과 정렬되지 않은 부분을 유지하며 동작합니다.

 

선택 정렬은 다음과 같은 과정을 따릅니다:

1. 주어진 리스트에서 가장 작은(또는 큰) 원소를 찾습니다.
2. 해당 원소를 리스트의 맨 앞으로 이동시킵니다.
3. 정렬된 부분과 정렬되지 않은 부분을 나누어 위 과정을 반복합니다.
4. 리스트의 모든 원소가 정렬될 때까지 위 과정을 반복합니다.

 

선택 정렬 코드 예시 (C#)

 

아래 코드는 C#으로 작성된 선택 정렬 알고리즘의 예시입니다. 입력 배열이 {64, 25, 12, 22, 11}일 때, 이를 선택 정렬하여 오름차순으로 정렬한 결과를 출력합니다.

 

using System;

class SelectionSort {

    static void Selection_Sort(int[] arr) {
        int n = arr.Length;
        for (int i = 0; i < n - 1; i++) {
            int min_idx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[min_idx]) {
                    min_idx = j;
                }
            }
            
            // Swap the found minimum element with the first element
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;

            // Print intermediate result
            Console.Write("Iteration " + (i+1) + ": ");
            foreach (int num in arr) {
                Console.Write(num + " ");
            }
            Console.WriteLine();
        }
    }

    static void Main() {
    
        int[] arr = { 64, 25, 12, 22, 11 };
        
        Console.WriteLine("Original array:");
        foreach (int num in arr) {
            Console.Write(num + " ");
        }
        Console.WriteLine();

        Selection_Sort(arr);
        
        Console.WriteLine("Sorted array:");
        foreach (int num in arr) {
            Console.Write(num + " ");
        }
    }
}

 

 

위 코드를 실행한 결과는 다음과 같습니다.

 

Original array:
64 25 12 22 11 
Iteration 1: 11 25 12 22 64 
Iteration 2: 11 12 25 22 64 
Iteration 3: 11 12 22 25 64 
Iteration 4: 11 12 22 25 64 
Sorted array:
11 12 22 25 64

 

 

 

 

선택 정렬 장단점

 

- 장점

• 구현이 간단하고 이해하기 쉽습니다.
• 작은 크기의 리스트에 대해서는 효율적입니다.
• 추가 메모리 공간이 필요하지 않습니다.

- 단점

• 시간 복잡도가 O(n^2)으로 비효율적입니다. 따라서 큰 규모의 리스트에 대해서는 성능이 좋지 않습니다.
• 이미 정렬되어 있는 경우에도 원소를 비교하므로 비효율적입니다.

 

선택 정렬 사용 사례

 

• 작은 크기의 리스트를 정렬해야 할 경우 : 선택 정렬은 구현이 간단하므로 작은 크기의 리스트를 정렬할 때 유용합니다.
• 메모리가 제한된 환경일 경우 : 추가 메모리 공간이 필요하지 않기 때문에 메모리가 제한된 환경에서 선택 정렬을 사용할 수 있습니다.
• 이미 정렬된 리스트를 정렬할 필요가 없을 경우: 이미 정렬된 리스트를 정렬할 필요가 없는 경우에는 선택 정렬을 사용하여 비효율성을 줄일 수 있습니다.

 

 

선택 정렬은 간단하고 직관적인 정렬 알고리즘으로, 작은 규모의 리스트를 정렬하는 데 적합합니다. 그러나 큰 규모의 리스트에 대해서는 효율성이 떨어지므로, 대규모 데이터를 정렬해야 할 때는 다른 정렬 알고리즘을 고려하는 것이 좋습니다.