C# 선택 정렬(Selection Sort)에 대해서

선택 정렬

최소값을 선택해서 맨 앞의 값과 교체한다. 그래서 선택 정렬이다!

 

• 주어진 리스트 중에 최소값을 찾는다.
• 그 값을 맨 앞에 위치한 값과 교체한다.
• 맨 처음 위치를 뺸 나머지 리스트를 같은 방법으로 교체한다.
• 정렬 완료

시간 복잡도와 공간 복잡도

• 최고 시간 복잡도: O(n^2)
• 평균 시간 복잡도: O(n^2)
• 최악 시간 복잡도: O(n^2)
• 최고 공간 복잡도: O(1)

 

수도 코드

Initialize n = Length of Array
SelectionSort (Array, n)
{
    for i = 0 to n-2
    {
        i_min = i
        for j = i+1 to n-1
        {
            if Array[j] < Array[i_min]
                i_min = j
        }
        Swap(Array[j], Array[i_min])
    }
}

 

예제 코드

static void Main(string[] args)
{
    var array = new int[] { 3, 7, 2, 5, 1, 4 };

    Console.WriteLine($"{string.Join(" ", array)} << 시작");

    SelectionSort(array);
}

public static int[] SelectionSort(int[] array)
{
    int count = 0;
    var min = array.First();

    for (int i = 0; i < array.Length; i++)
    {
        for (int j = count; j < array.Length; j++)
        {
            if (array[j] < min)
            {
                min = array[j];
            }
        }

        var index = Array.IndexOf(array, min);

        var temp = array[count];
        array[count] = array[index];
        array[index] = temp;

        count++;
        min = array.Last();

        Console.WriteLine(string.Join(" ", array));
    }

    return array;
}

 

개선된 예제 코드

i와 동일한 역할을 하는 count 제거 >> i로 대체

min값이 아닌 minIndex로 변경

 

static void Main(string[] args)
{
    var array = new int[] { 3, 7, 2, 5, 1, 4 };

    Console.WriteLine($"{string.Join(" ", array)} << 시작");

    SelectionSort(array);
}

public static int[] SelectionSort(int[] array)
{
    for (int i = 0; i < array.Length; i++)
    {
        var minIndex = i;
        for (int j = i + 1; j < array.Length; j++)
        {
            if (array[j] < array[minIndex])
            {
                minIndex = j;
            }
        }

        var temp = array[minIndex];
        array[minIndex] = array[i];
        array[i] = temp;

        Console.WriteLine(string.Join(" ", array));
    }

    return array;
}

 

 

 

버블 정렬(Bubble Sort)

선택 정렬(Selection Sort)

 

함께 보면 좋은 글

C# 버블 정렬(Bubble Sort)에 대해서

C# 삽입 정렬(Insertion Sort)에 대해서

 

참고 사이트

Selection Sort - Fully Understood