선택 정렬 (Selection Sort)

안녕하세요. 연두아빠에요.

자료구조 포스팅 첫번째 주제로 기초 정렬 알고리즘을 훑고 지나가보려고 합니다.

첫번째 정렬 알고리즘은 선택 정렬입니다.

가장 기초적인 정렬 알고리즘이라고 할 수 있겠죠.

선택 정렬은 아마 초등학생들을 상태로 이 숫자를 정렬해보라고 하면,

아마 십중팔구 이 방식을 이용해서 정렬을 할 것이라고 생각 될 정도로 단순한 방법입니다.

정렬 알고리즘에 있어 대부분 단순하다는 말은 곧 비효율 적이라는 말과 동일합니다.

계속해서 선형 탐색(Linear Scan)하며 반복해서 가장 작은 숫자를 찾아 앞으로 보내는게 끝입니다.

그림을 보며 따라가보면 쉽게 이해될 것 같습니다.

위와 같이 정렬이 되어 있지 않은 다섯 개의 숫자가 있습니다.

선택 정렬은 그냥 맨 앞에서 부터 가장 작은 숫자를 찾는 것을 반복하면 됩니다.

가장 첫번째 숫자인 5를 기준으로 가장 작은 숫자는 1입니다.

5와 1을 교환하여 1을 맨 앞으로 보냅니다.

1을 맨 앞으로 보낸 후 다음 숫자인 3을 기준으로 가장 작은 수인 2를 찾아 바꿉니다.

3번째에 위치한 5를 기준으로 다시 한번...

마지막으로 한번 더 해주면...

이걸로 모든 정렬이 끝나게 되네요.

가장 쉽고 단순한 정렬 알고리즘인 만큼 매우 비효율적이라는게 느껴지네요.

배열이 어떻게 되어있던지간에 전체 비교를 진행하므로 시간복잡도는 O(n²)가 됩니다.

지난번 언급했던대로 O(n²)부터는 제법 비효율적이라고 보셔도 됩니다.

빅오 표기법(Big-O Notation)이 기억나지 않으시는 분은 아래 링크로 이동하셔서 복습해 보세요.

    Big O 표기법 (Big O Notation), 시간 복잡도 표기법 (Time Complexity Notation)

선택 정렬 알고리즘을 C# 코드로 구현을 해보면 다음과 같습니다.

void SelectionSort (List<int> data)

{

    for (int i = 0; i < data.Count - 1; ++i)

    {

        for (int j = i + 1; j < data.Count; ++j)

        {

            if (data[i] >= data[j])

            {

                data.Swap(i, j);

            }

        }

    }

}

위와 같이 이중 for문으로 구현이 되기 때문에 O(n²)의 시간 복잡도를 갖게 됩니다.

그 외에 더 알고 싶은 점이나 의문이 생기는 부분들 댓글로 남겨드리면 최대한 도움을 드려볼께요.

공감(♥) 및 댓글은 글쓴이에게 커다란 힘이 됩니다.

길지 않은 이 글을 쓰는데 나름 몇 시간이 걸렸어요^^;

저에게 1초만 시간을 내주셔서 공감 버튼 꾸욱 눌러주세요^^

제 블로그를 방문해 주신 모든 분들 사랑합니다^^

이상입니다. 감사합니다!