선택 정렬 (C#)

개요

선택 정렬은 첫번째 자료를 두번째 자료부터 마지막 자료까지 차례대로 비교하여,

가장 작은 값을 찾아 첫번째에 놓고, 두번째 자료를 세번째 자료부터 마지막 자료까지와 차례대로 비교하여

가장 작은 값을 찾아 두번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.

 

1회 정렬을 수행하고 나면 가장 작은 값의 자료가 맨 앞으로 오게 되므로, 그 다음 회부터는 두번째 자료로 비교한다.

마찬가지로 3회 째 부터는 3번째 자료부터 비교한다.

 

과정

1. 주어진 배열 중에서 최솟값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
4. 하나의 원소만 남을 때까지 위의 1~3 과정을 반복한다.

시간복잡도

O(N²)

가장 작은 것을 선택할 때 N번,

앞으로 보낼 때에 N번의 연산을 한다.

 

코드

class 선택정렬
    {
        static void Main(string[] args)
        {
            int max = 999;
            int min, index = 0;
 
            int[] array = { 10, 9, 6, 3, 8, 1 };
 
            
            for(int i = 0; i < array.Length; i++)
            {
                min = max;
                //작은 수를 앞으로 보내므로 i 부터 시작
                for (int j = i; j < array.Length; j++)
                {
                    if (min > array[j])
                    {
                        min = array[j];
                        index = j;
                    }
                }
                Swap(ref array[i], ref array[index]);
            }
            
            for (int i = 0; i < array.Length; i++)
                Console.WriteLine(array[i]);
            
        }
 
        private static void Swap (ref int a , ref int b)
        {
            int temp = a;
            a = b;
            b = temp;
        }
 
    }