Selection Sort Algorithm (선택 정렬 알고리즘)

정렬(Sorting)은 리스트의 아이템을 오름차순 혹은 내림차순으로 정렬하는 것을 말한다.

정렬은 사람, 컴퓨터 모두가 리스트에 있는 아이템을 빨리 찾을 수 있도록 도와준다.

Swap

정렬을 하기위해서는 swap(자리 바꾸기)을 할 줄 알아야 한다.

namespace Rextester {
    class Program {
        public static void Main(string[] args) {
            int[] array = { 1, 2, 3, 4, 5 };
 
            Console.WriteLine("Before swap()");
            printArray(array);
            Console.WriteLine("After swap()");
            swap(array, 0, 4);
            printArray(array);
            
        }
 
        public static void swap(int[] array, int index1, int index2) {
            int temp = array[index1];
            array[index1] = array[index2];
            array[index2] = temp;
        }
 
        public static void printArray(int[] array) {
            for (int i = 0; i < array.Length; i++){
                Console.Write("{0} ", array[i]);
            }
            Console.WriteLine("");
        }
    }
}

다음은 swap의 예제다(C#).

swap은 앞의 수를 임시로 복사 해 놓고 바꿔 대입하는 방식이다.

Selection Sort

sort에는 여러가지 종류가 있다.

간단한 sort 방법으로는 Selection Sort라 불리는 것이 있다.

이 알고리즘은 계속해서 다음으로 작은 원소를 선택(select)하기 때문에 Selection Sort라 불린다.

의사코드로 살펴보자.

1. 리스트 중 가장 작은 수의 원소를 찾고 그것을 제일 첫번째 원소와 바꾼다(swap).

2. 다음은 두번째로 작은 수의 원소를 찾고 2번째 원소와 바꾼다.

3. n번째로 작은 수의 원소를 찾고 n번째 원소와 바꾼다.

namespace Rextester
{
    class Program {
        public static void Main(string[] args) {
            int[] array = { 22, 11, 99, 88, 9, 7, 42 };
 
            Console.WriteLine("Before swap()");
            printArray(array);
            Console.WriteLine("After swap()");
            selectionSort(array);
            printArray(array);
            
        }
        
        public static void selectionSort(int[] array) {
            int minIndex = 0;
            for (int i = 0; i < array.Length; i++) {
                minIndex = indexOfMinimum(array, i);
                swap(array, i, minIndex);
            }
        }
        
        public static int indexOfMinimum(int[] array, int startIndex) {
            int minValue = array[startIndex];
            int minIndex = startIndex;
            for (int i = startIndex; i < array.Length; i++) {
                if (array[i] < minValue) {
                    minValue = array[i];
                    minIndex = i;
                }
            }
            return minIndex;
        }
        
        public static void swap(int[] array, int firstIndex, int secondIndex) {
            int temp = array[firstIndex];
            array[firstIndex] = array[secondIndex];
            array[secondIndex] = temp;
        }
 
        public static void printArray(int[] array) {
            for (int i = 0; i < array.Length; i++){
                Console.Write("{0} ", array[i]);
            }
            Console.WriteLine("");
        }
    }
}

다음은 선택 정렬을 구현해본 것이다.

swap()함수는 앞서 구현한 swap() 예제의 것을 그대로 사용했다.

indexOfMinimum은 startIndex(시작지점)부터 리스트의 맨 끝까지 살펴보면서

가장 작은 수를 찾아내 그 수가 있는 자리를 리턴하고,

selectionSort에서는 indexOfMinimum이 리턴한 자리와 현재 자리를 순차적으로 바꾸면서 리스트를 정렬한다.

수행결과는 다음과 같다.

선택 정렬은 효과적인 알고리즘일까?

프로그램 수행 시간이 실행되는 코드 수와 관련이 있다는 것을 감안 할 때,

8개의 원소가 있는 array에서 selection sort에 수행되는 코드라인 수는 36번이다.

selectionSort()에서 for loop을 돌면서 매번 indexOfMinimum()에서 다시 array를 돌기 때문에

상당히 비 효율적이라고 할 수 있다.

따라서 선택정렬은 효과적인 알고리즘은 아니다.

자세한 정보는 (http://www.sorting-algorithms.com/)에 있다.