[Sort] Selection Sort

Selection Sort(선택 정렬)은 앞서 다룬 Bubble Sort와 마찬가지의 복잡도를 가진다. 그러므로 많은 데이타의 정렬 위해서 쓰기에는 그 퍼포먼스가 현저하게 떨어진다.

하지만 Bubble Sort와 마찬가지로 그 구현 방법에 있어서 빠르기 때문에 작은 단위의 데이타 정렬에서 이용하기에 적합하다고 할 수 있다.

Selection Sort는 배열(혹은 리스트)에서 가장 작은 값을 찾아내어 그 값을 최앞단에 위치 시키는 방식이다.

Sort 대상 : 8 5 1 9 2

이렇게 5개의 숫자가 있다고 가정했을 때 다음과 같은 과정을 보인다.

8 5 1 9 2          => 최소값을 찾아낸다
1 5 8 9 2          => 1과 비교 대상의 첫번째 인덱스와 바꾼다.
5 8 9 2             => 최소값이 맨 앞단으로 옮겨졌기 때문에 인덱스를 증가하여 비교한다.
2 8 9 5             => 다시 최소값을 찾아 비교 대상의 첫번째 인덱스와 바꾼다.
8 9 5               => 인덱스를 증가하여 다시 비교한다.

위 과정을 배열의 마지막까지 진행을 하게 되면 정렬이 완료된다.

다음은 프로그램으로 나온 과정이다.

8 , 5  ,1 , 9 , 2
1 , 5 , 8 , 9 , 2
1 , 2 , 8 , 9 , 5
1 , 2 , 5 , 9 , 8
1 , 2 , 5 , 8 , 9
1 , 2 , 5 , 8 , 9

php로 만든 예제

[code php]
<?php
    $a = array( 8 , 5 , 1 , 9 , 2);
   
    SelectionSort(& $a);

    function SelectionSort($array)
    {
        $loop_count = count($array);
       
        for($i = 0 ; $i < $loop_count ; $i++)
        {
            $min = $array[$i];
            $minIndex = $i;
       
           /* 최소값을 찾기 위하여 루프를 돌린다. */
            for($j = $i ; $j < $loop_count ; $j++)
            {
                if($array[$j] < $min)
                {
                    $min = $array[$j];
                    $minIndex = $j;            
                }
            }
           
            swap(& $array[$i] , & $array[$minIndex]);
           
            echo implode(' , ' , $array) . "<br/>";
        }       
    }

    function swap($a , $b)
    {
        $tmp = $b;
        $b = $a;       
        $a = $tmp;               
    }

?>
[/code]

C++로 구현한 예

[code cpp]
#include <iostream>
using namespace std;

void swap(int *a , int *b)
{
    int *tmp = b;   
    b = a;
    a = tmp;
}

int main()
{
    int a[5] = {8 , 5 , 1 , 9 , 2};

    int loop_count = (sizeof(a) / sizeof(a[0]));
    int min , minIndex;
   
    for(int i = 0 ; i < loop_count ;i++)
    {
        min = a[i];
        minIndex = i;
       
        for(int j = i ; j < loop_count ; j++)
        {
            if(a[j] < min)
            {
                min = a[j];
                minIndex = j;
            }
        }
       
        swap(a[i] , a[minIndex]);
    }
   
    cout << a[0] << endl;
   
    return 0;
}
[/code]