📒 갈무리 - 선택정렬(Selection sort)

📌 선택정렬이란?

- 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해 나가는 방식의 정렬 방법이다.

 

📌 선택정렬의 과정

1. 리스트에서 최소값을 찾는다.

2. 최소값을 맨 앞의 값과 교체한다.(Swap)

3. 교체된 위치를 제외한 나머지 리스트를 같은 방법으로 교체해 나간다.

 

📌 직접 구현해 보자...

// C# 선택정렬 구현

    class Sort
    {
        public int[] NumberSort(int[] numbers)
        {
            for (int i = 0; i < numbers.Length; i++)
            {
                for (int j = i + 1; j < numbers.Length; j++)
                {
                    if (numbers[i] > numbers[j])
                    {
                        int minNumberTemp = numbers[j];
                        numbers[j] = numbers[i];
                        numbers[i] = minNumberTemp;
                    }
                }
            }
            return numbers;
        }
        // 가독성을 위해 각 기능마다 함수로 분리하면 좋지만, 지금은 편의상 간단하게 구현함
    }

 

📌 선택정렬의 특징

- 구현은 단순하지만 비효율적인 방법이다.

- 두 개의 for 문의 실행 횟수

- 비교하는 과정이 상수 시간이라는 가정 아래, n개의 주어진 리스트를 선택정렬로 정렬한다면 O(n²)의 시간이 걸린다.