선택정렬에 대한 이해

정렬이란?

ko.khanacademy.org

정렬이란

데이터를 내림차순 오름차순으로 정렬해놓으면 컴퓨터가 어떤 항목을 찾을 때 이진검색과 같은 알고리즘을 이용해 빠르고 편리하게 찾을 수 있습니다.

스왑함수의 구현

선택정렬 알고리즘을 포함해서, 정렬 알고리즘에서 중요한 것은 배열 내 두 개 항목의 위치를 바꾸는 것입니다. 간단하게 스왑함수를 구현해보는 연습을 해보겠습니다. 먼저 개별적으로 연습해봤습니다.

    static void Main()
    {
        int[] twoNumber = new int[2];
        string[] number = Console.ReadLine().Split(',');
        twoNumber[0] = int.Parse(number[0]);
        twoNumber[1] = int.Parse(number[1]);
        SwapAndSqr(twoNumber[0], twoNumber[1]);
    }


    static void SwapAndSqr(int a, int b)
    {
        int tmp = b;
        b = a;
        a = tmp;
        Console.WriteLine("{0},{1}", a, b);
    }

칸 아카데미의 문제도 풀어봅니다.

잘 풀렸습니다.

선택정렬 의사코드

선택 정렬은 수열을 정렬하는 알고리즘 중 하나입니다. 선택정렬은 수열을 선형탐색을 하여 최솟값을 찾아내고 최솟값을 왼쪽 끝에 있는 숫자와 교환합니다. 그리고 정렬된 왼쪽 끝 최솟값에 대해선 아무런 작업도 하지 않습니다. 이와 같은 동일한 작업을 정렬이 완료될때까지 반복합니다.

선택 정렬 의사코드

ko.khanacademy.org

위 링크에 있는 미니게임을 통해 쉽게 이해할 수 있습니다. 10가지 카드를 정렬하는데 꽤 오랜 시간이 걸립니다. 선택 정렬은 오래 걸립니다. 큰 데이터를 분류하는데 적합하지 않습니다.

하위 배열에서의 가장 작은 요소의 인덱스 알아내기

선택 정렬을 구현하려 할 때 처음 최솟값을 정렬하기는 쉽습니다. 1, 5, 7, 0, 3이란 배열이 있으면 그저 최솟값인 0을 1과 바꿔주기만 하면 됩니다. 그 후 두 번째로 작은 수를 정렬할때는 조금 복잡할 수 있습니다.

가장 작은 값은 이미 인덱스0과 바꾸었기 때문에 인덱스1부터 시작하는 배열의 일부분에서 최솟값을 찾아야합니다. 이런 경우를 '하위배열'의 선택이라 합니다.

그럼 하위 배열에서 가장 작은 요소를 찾아보는 코드를 작성해보겠습니다.

    static int IndexOfMinimum(int[] numbers, int startIndex)
    {
        int minValue = numbers[startIndex];
        int minIndex = startIndex;

        for (int i = startIndex; i < numbers.Length; i++)
        {
            if(minValue > numbers[i])
            {
                minValue = numbers[i];
                minIndex = i;
            }
        }

        Console.WriteLine("{0}번째부터의 최솟값의 Index : {1}", startIndex, minIndex);
        return minIndex;
    }

선택정렬 구현하기

그럼 지금까지 연습했던 스왑함수, 하위 배열에서 가장 작은 요소 인덱스 알아내기를 이용하여 선택정렬을 구현해보겠습니다.

    static int[] SelectionSort(int[] numbers)
    {
        //int minIndex = 0;

        for (int i = 0; i < numbers.Length; i++)
        {
            int minIndex = IndexOfMinimum(numbers, i);
            Swap(numbers, i, minIndex);
        }

        return numbers;
    }

마지막으로 지금까지 작성했던 Swap함수와 IndexOfMinimum함수로 선택정렬을 구현했습니다.

선택정렬의 분석

자, 마지막으로 선택정렬이 얼마만큼의 시간을 가지는지 점근적 표기법으로 알아보겠습니다. 그 전에 선택정렬의 일반식이 어떤지 분석해보겠습니다.

위 예제를 보면 배열의 크기가 8일 때 반복문이 실행되는 횟수는 36번입니다. 이 식을 정리해보면 아래와 같습니다.

(8+1)+(7+2)+(6+3)+(5+4) = 9 + 9 + 9 + 9 = 4*9 = 36

가장 작은 수와 가장 큰 수 끼리 짝찌어 서로 더하고, 짝지을 수의 개수만큼 곱해주면 위와같은 결과가 나옵니다.

예외의 경우는 짝이 지어지지 않은 홀수가 있는 경우인데, 이때 홀수는 한쌍의 반으로 생각하여 계산하면 됩니다. 예를 들어 배열의 크기가 5개라면 2쌍하고 수 한개가 남으니, 2.5쌍의 수가 나옵니다. 이를 계산해보면 2.5*6 = 15가 됩니다.

이렇게 1부터 n까지 나열된 수열을 수학에서 '등차급수'라 부릅니다. 여기서 가장 작은 수와 가장 큰 수의 합은 n+1입니다. 수가 총 n개만큼 있으므로 n/2쌍을 구할 수 있습니다. 따라서 1부터 n까지의 합은 (n+1)*(n/2)로 표현이 가능합니다.

이걸 풀어쓰면 n^2/2+n/2이입니다.

그럼 마지막으로 실행시간을 구해보겠습니다.

1. Swap함수 : 스왑은 n번 호출되고 늘 같은 시간이 소요됩니다. 점근적 표기법에 따라 Θ(n)이라고 말할 수 있습니다.

2. SelectionSort함수 : 마찬가지로 Swap함수와 IndexOfMinimum함수를 호출 할 뿐 똑같이 n번 반복하기 때문에 Θ(n)이라 할 수 있습니다.

3. IndexOfMinimun함수 : 앞서 계산한것과 같이 n^2/2+n/2 이란 식이 나옵니다. 여기서 점근적 표기법으로 유효한 항은 n^2이며 Θ(n^2)이란 값이 나옵니다.

1,2,3번 중에서 가장 유요한 항은 Θ(n^2)이기 때문에 최종적으로 선택정렬의 시간은 Θ(n^2)라고 정의 할 수 있습니다.

마지막 과제

마지막 과제는 선택정렬의 시각화입니다. 따로 고민해보고 콘솔앱 혹은 유니티로 선택정렬을 시각화해보는 시간을 가져보겠습니다. 이상입니다.

저작자표시

모름