선택 정렬(Selection Sort)

선택정렬을 구현하면 다음과 같다.

(출처 : http://seleccionenc.blogspot.kr/ )

#include <iostream>
#define swap(a,b) {int tmp = a; a = b; b = tmp;}
 
using namespace std;
 
int main()
{    
    int n[10];
    
    for(int i = 0 ; i < 10 ; i ++) cin >> n[i];
    
    for(int i = 0 ; i < 10 ; i ++)
    {
            int min = i;
            for(int j = i ; j < 10 ; j ++)
            {
                    if(n[min] > n[j])
                    {
                            min = j;
                    }
            }            
            swap(n[i],n[min]);
    }
    
    for(int i = 0 ; i < 10; i ++) printf("%d ",n[i]);
 
    return 0;
}

그렇다면 위 코드와 아래코드는 어떤 면에서 다른가?

아래코드는 위 코드에 비해 코드의 가독성이 좋지만, 같은 2중 for문일지라도 시간복잡도 면에서 밀리는 것을 볼 수 있다.

하지만 적은 값을 Sort할때는 좀 더 보기좋은  아래의 코드가 유용할 것 같다.

#include <iostream>
#define swap(a,b) {int tmp = a; a = b; b = tmp;}
 
using namespace std;
 
int main()
{    
    int n[10];
    
    for(int i = 0 ; i < 10 ; i ++) cin >> n[i];
    
    for(int i = 0 ; i < 10 ; i ++)
    {
            for(int j = i ; j < 10 ; j ++)
            {
                    if(n[i] > n[j])
                    swap(n[i],n[j]);
            }            
    }
    
    for(int i = 0 ; i < 10; i ++) printf("%d ",n[i]);
 
    return 0;
}