알고리즘 2(선택정렬)

안녕하세요

 

게임개발자가 되기위해 공부하고 있는 구구입니다.

오늘은 자료구조에서 선택정렬에 대해 알아보도록 하겠습니다.

---

• 선택 정렬(Selection sort)

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

 

• 하는 방법

1. 리스트에서 최솟값을 찾는다.
2. 최솟값을 맨앞의 값과 교체한다.(Swap)
3. 교체한 맨 앞의 데이터는 정령된 것으로 간주, 다음 인덱스부터 1, 2의 행위를 반복

 

 

 

 

 

• 선택 정렬의 특징

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

- 두 개의 for 루프의 실행 횟수

 

 

• 시간복잡도

- O(n^2)

 

최악의 경우 없이 기존의 데이터의 구성에 따라 비교횟수가 변하지 않습니다.

 

1회차 : n-1, 2회차 : n-2, ····· n-1회차 : 1

따라서 비교하는 횟수를 전부 합치면 1부터 n-1까지의 등차수열의 합이기 때문에 n의 2차식꼴이 나옵니다.

 

 

• 정렬 코딩

 

// 정렬
            for (int i = 0; i < data.Length; i++)
            {
                int min = i; //제일 작은 값 index

                for (int j = i + 1; j < data.Length; j++) //j는 비교할값 index
                {
                    // 최소값 비교
                    if (data[min] > data[j])
                    {
                        min = j;
                    }//최솟값이 j인덱스의 데이터라면 최솟값 인덱스 변경
                }

                Swap(ref data[i], ref data[min]);

                Console.Write((i + 1) + "번째 정렬값(" + data[i] + ", " + data[min] + ") - ");

                for (int k = 0; k < data.Length; k++)
                {
                    Console.Write(data[k] + ",");
                }
            }

 

 

• Swap 함수

static void Swap(ref int a, ref int b) //참조형으로 해야 함수를 빠져나가도 값이 바뀐게 저장됨
{
        int temp = a;
        a = b;
        b = temp;
}

 

 

• Big - O 표기법

1. O(1)
2. O(log n)
3. O(n)
4. O(n log(n))
5. O(n^2)

반복문 한번당 n승

-> 반복문 2번이면 n^2

 

5로 갈수록 시간복잡도가 커서 좋지 않음.