선택 정렬 : Selection sort

정렬 알고리즘은 컴퓨터 과학의 많은 응용 프로그램에서 중추적인 역할을 합니다. 가장 이해하기 쉬운 것은 선택 정렬 알고리즘입니다. 대규모 데이터 세트에 대해 가장 효율적이지는 않지만 선택 정렬의 단순성은 더 복잡한 알고리즘을 학습하기 위한 견고한 기반을 제공합니다. 이 블로그 게시물에서는 선택 정렬의 기본 이론을 살펴보고 C#에서 구현하는 과정을 안내합니다.

선택 정렬 이해

선택 정렬은 비교 기반 정렬 알고리즘입니다. 알고리즘의 기본 아이디어는 입력 목록을 정렬된 부분과 정렬되지 않은 부분의 두 부분으로 나누는 것입니다. 처음에는 정렬된 부분이 비어 있고 정렬되지 않은 부분에는 모든 요소가 포함되어 있습니다. 알고리즘은 정렬되지 않은 부분에서 가장 작은(또는 정렬 순서에 따라 가장 큰) 요소를 반복적으로 선택하여 정렬된 부분의 끝으로 이동합니다. 이 작업은 정렬되지 않은 부분이 비어 있고 정렬된 부분이 원하는 정렬 순서로 모든 요소를 포함할 때까지 반복적으로 수행됩니다.

선택 정렬 실행

다음 정수 배열을 고려하십시오. [29, 10, 14, 37, 13]

이 배열에 대한 선택 정렬 단계는 다음과 같습니다.

1. 배열에서 가장 작은 요소인 10을 찾아 첫 번째 요소와 바꿉니다: [10, 29, 14, 37, 13]
2. 나머지 배열에서 가장 작은 요소인 13을 찾아 두 번째 요소와 바꿉니다: [10, 13, 14, 37, 29]
3. 가장 작은 나머지 요소 14를 찾아 세 번째 요소 [10, 13, 14, 37, 29]로 바꿉니다. 14는 이미 올바른 위치에 있으므로 바꿀 필요가 없습니다.
4. 어레이가 정렬될 때까지 이 프로세스를 계속합니다.

선택 정렬 구현하기

다음은 C#에서 선택 정렬의 기본 구현입니다.

public void SelectionSort(int[] arr)
{
    int n = arr.Length;

    for (int i = 0; i < n - 1; i++)
    {
        // Assume the min is the first number
        int minIndex = i;
        for (int j = i + 1; j < n; j++)
        {
            // If we find a smaller number, update minIndex
            if (arr[j] < arr[minIndex])
            {
                minIndex = j;
            }
        }

        // If minIndex isn't the first number, swap it with the first number
        if (minIndex != i)
        {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

시간 복잡도

선택 정렬은 n 요소의 배열에 대해 n-1 패스를 만듭니다. 각 패스에서 최대 한 번의 스왑을 수행합니다. 시간 복잡도는 최고, 평균 및 최악의 경우 O(n^2)이므로 QuickSort, MergeSort 또는 HeapSort와 같은 다른 정렬보다 큰 목록에서 덜 효율적입니다.

결론

O(n^2) 시간 복잡성으로 인해 큰 데이터 세트에는 적합하지 않지만 선택 정렬은 작은 배열이나 교육 목적에 간단하고 유용한 알고리즘입니다. 이것은 정렬의 원리와 더 복잡한 정렬 알고리즘의 기능을 이해하는 훌륭한 디딤돌입니다.