[알고리즘] 선택 정렬 ( Selection Sort )

1. 개념

정렬하고자 하는 배열중 최소의 값을 찾아 차례 차례 순서에 따라 값을 교체 해주는 방식으로 최소값을 찾는 시간은

처음 찾을때 보다 정렬이 진행 될수록 찾는 시간이 단축되는 구조 입니다.

  - 검색 시작지점은 배열의 인덱스 0부터 시작하며 진행순서에 따라 시작지점 인덱스는 1씩 증가

  - 최소값 또는 최대값을 가진 인덱스를 찾고 시작 인덱스와 교환

위의 사진처럼 오름차순으로 정렬을 진행할때 회차에 따라 시작인덱스는 1씩증가되며 시작인덱스 외의 나머지 인덱스들을

검색하여 가장 작은 값을 찾아 교환해주는 방식으로 진행됩니다.

2. C# 코드

using System;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] nArr = new int[]{ 1, 4, 3,  5, 9, 6, 2, 7, 8, 10 };
            int TargetIndex, temp;

            //배열의 마지막 값은 자연스럽게 정렬이 되므로 배열크기 -1 만큼 반복
            for(int i = 0; i < nArr.Length-1; i++)
            {
                //정렬방식에 따라 교환이 이루어질 인덱스
                TargetIndex = i;

                //비교대상 인덱스는 시작인덱스 +1 에서 배열의 마지막까지 반복
                for(int j = i+1; j < nArr.Length; j++)
                {
                    //정렬방식 < : 오름차순, > : 내림차순
                    if (nArr[j] < nArr[TargetIndex])
                        TargetIndex = j;
                }
                
                if( i != TargetIndex)
                {
                    //검색을 시작한 가장 앞쪽 인덱스와 교환
                    temp = nArr[i];
                    nArr[i] = nArr[TargetIndex];
                    nArr[TargetIndex] = temp;
                }
            }

            for (int i = 0; i < nArr.Length; i++)
                Console.Write(nArr[i] + "\t");
        }
    }
}

결과

1    2    3    4    5    6    7    8    9    10

3. 장단점

장점

    - 비교적 쉬운 코드로 구현 가능

    - 정렬이 진행됨에 따라 속도는 빨라짐

    - 버블 정렬보다 값의 복사와 이동이 적어 비교적 빠름

단점

    - 데이터의 크기가 커질수록 효율이 떨어짐

    - 데이터 정렬 속도가 고정적으로 n의 제곱만큼 걸려 더이상의 정렬 속도를 기대할수 없음

정렬 알고리즘 테스트

종류	최소	최대	정렬시간 (10만개 테스트)
퀵 정렬	n log n	n2	32 ms
삽입 정렬	n	n2	8142 ms
선택 정렬	n2	n2	13499 ms
버블 정렬	n2	n2	53488 ms

시간적인 측면에서는 고정적으로 정렬시간이 안정적이지만 더이상의 속도를 낼수 없고 구현이 간단한 정렬방식의

구조적 한계 때문에 비효율적인 방법 입니다.

4. 관련글

• 버블 정렬 ( Bubble Sort ) Post 참고
• 삽입 정렬 ( Insertion Sort ) Post 참고
• 퀵 정렬 ( Quick Sort ) Post 참고