[Algorithm] 선택 정렬(Selection Sort)에 대해 알아보자!

이번에 다룰 내용은 여러 정렬 알고리즘 중 하나인 선택정렬이다.

 

바로 선택정렬의 개념부터 알아보자.

 

선택정렬이란?

첫번째 인덱스부터 모든 인덱스를 검사하여 최소값을 찾아 정렬하는 방식이다.

그렇기 때문에 입력된 데이터가 정렬이 되어있건, 역순이건, 반쯤 정렬이 되어있건 모두 같은 시간이 걸리게된다. 따라서 이 정렬의 시간복잡도는 O(n^2)가 되고 데이터 수가 커지면 커질수록 실행시간은 제곱으로 늘어나게 되는 형식인 것이다.

 

아래의 참고 이미지를 보면 이해가 쉽게 갈 것이라 생각한다.

https://dnmaxi.tistory.com/25

 

위의 참고 이미지처럼 끝까지 한번 돌고 최소 값을 찾아 교환(swap)하는 형식이다.

 

이런 방식의 장점고 단점에 대해서도 알아보자.

 

장점

• 코드 구현이 쉽다.
• 정렬이 진행됨에 따라 속도는 빨라지는 속성을 갖고있다.
• 버블 정렬보다 값의 복사와 이동이 적어 비교적 빠른편에 속한다.

 

단점

• a to z를 돌면서 최소값을 찾기때문에 데이터의 크기가 커질수록 효율이 떨어진다.
• 데이터의 정렬 속도가 O(n^2)로 고정적으로 걸리기때문에 퀵, 삽입 정렬 등에 비해 속도가 좋은편에 속하지 못한다.

 

정렬 알고리즘 테스트 결과

 

이제 아래의 구현 소스를 보고 이해해보자.

(C# Source)

using System;


namespace Jeongkyun_SelectionSort
{
    public class Program
    {
        public static void Main(string[] args)
        {
            int[] nArr = new int[] { 1, 7, 5, 34, 5, 2, 23, 54, 1 };
            nArr = arr_swap_select_sort(nArr);
            Print(nArr);

            Console.ReadKey();
        }

        /// <summary>
        /// 선택 정렬 + SWAP 로직 구현 함수
        /// </summary>
        /// <param name="arr">기존 배열 값을 담아둔 변수</param>
        static int[] arr_swap_select_sort(int[] arr)
        {
            int min_idx, temp = -1;

            for (int i = 0; i < arr.Length; i++)
            {
                min_idx = i;

                for (int j = i + 1; j < arr.Length; j++)
                {
                    if (arr[j] < arr[min_idx])
                        min_idx = j;
                }

                temp = arr[min_idx];
                arr[min_idx] = arr[i];
                arr[i] = temp;
            }

            return arr;
        }

        /// <summary>
        /// Print 함수
        /// </summary>
        /// <param name="arr_val"></param>
        static void Print(int[] arr_val)
        {
            for (int i = 0; i < arr_val.Length; i++)
            {
                Console.Write(arr_val[i].ToString() + "\t");
            }
        }
    }
}