선택 정렬 (Select Sort)

Javascript로 구현한 Select sort

주어진 배열 이외에 다른 저장공간을 필요로 하지 않는 제자리 정렬 알고리즘의 하나로 시간 복잡도는  입니다. 어떤 상황에서든 에 비례하는 시간이 걸립니다.

1 5 6 8 7 4 3 9 2

1 5 6 8 7 4 3 9 2

1 2 6 8 7 4 3 9 5

1 2 6 8 7 4 3 9 5

1 2 3 8 7 4 6 9 5

1 2 3 8 7 4 6 9 5

1 2 3 4 7 8 6 9 5

1 2 3 4 7 8 6 9 5

1 2 3 4 5 8 6 9 7

1 2 3 4 5 8 6 9 7

1 2 3 4 5 6 8 9 7

1 2 3 4 5 6 8 9 7

1 2 3 4 5 6 7 9 8

1 2 3 4 5 6 7 9 8

1 2 3 4 5 6 7 8 9

소스코드

for(var i = 0 ; i < this.nodes.length - 1 ; ++i)
{
    var min = i;
 
    for(var j = i + 1 ; j < this.nodes.length ; ++j)
    {
        if(this.nodes[min].getSize() > this.nodes[j].getSize())
            min = j;
    }
 
    if(min == i)
        continue;
 
    var temp = this.nodes[i];
    this.nodes[i] = this.nodes[min];
    this.nodes[min] = temp;
 
    this.nodes[i].x = 5 + i * 55;
    this.nodes[min].x = 5 + min * 55;
}
 

안쪽 포문에서는 그 자리에 해당하는 최소값을 찾고 바깥쪽 포문에서는 딱 한번 swap 해줍니다. swap이 조금 일어나기때문에 거품정렬에 비해 속도가 빠릅니다. (그래도 ...)