거품 정렬 (Bubble Sort)

프로그래밍/알고리즘

거품 정렬 (Bubble Sort)

Cat체셔 2016. 5. 8. 17:47

Javascript로 구현한 Bubble sort

거품 정렬이란?
인접한 두 원소를 비교하여 정렬하는 방법입니다.
거품이 수면위로 떠오르는 것 처럼 보여서 붙혀진 이름이라고 합니다.
시간 복잡도는 입니다.

예시

1 5 6 8 7 4 3 9 2

1 5 6 7 8 4 3 9 2

1 5 6 7 4 8 3 9 2

1 5 6 7 4 3 8 9 2

1 5 6 7 4 3 8 2 9 첫번째 이터레이션 종료

1 5 6 7 4 3 8 2 9

1 5 6 4 7 3 8 2 9

1 5 6 4 3 7 8 2 9

1 5 6 4 3 7 2 8 9 두번째 이터레이션 종료

1 5 6 4 3 7 2 8 9

1 5 4 6 3 7 2 8 9

1 5 4 3 6 7 2 8 9

1 5 4 3 6 2 7 8 9 세번째 이터레이션 종료

1 5 4 3 6 2 7 8 9

1 4 5 3 6 2 7 8 9

1 4 3 5 6 2 7 8 9

1 4 3 5 2 6 7 8 9 네번째 이터레이션 종료

1 4 3 5 2 6 7 8 9

1 3 4 5 2 6 7 8 9

1 3 4 2 5 6 7 8 9 다섯번째 이터레이션 종료

1 3 4 2 5 6 7 8 9

1 3 2 4 5 6 7 8 9 여섯번째 이터레이션 종료

1 3 2 4 5 6 7 8 9

1 2 3 4 5 6 7 8 9 일곱번째 이터레이션 종료

1 2 3 4 5 6 7 8 9 여덟번째 이터레이션 종료

이터레이션 단위에서는 작은 수들은 앞으로 한칸씩 밀려오고 비교 단위에서는 큰 수들이 뒤로 한칸씩 밀려나는 형태입니다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for(var i = 0 ; i < this.nodes.length - 1 ; ++i)
{
    for(var j = 0 ; j < this.nodes.length - 1 - i ; ++j)
    {
        if(this.nodes[j].getSize() > this.nodes[j+1].getSize())
        {
            var temp = this.nodes[j];
            this.nodes[j] = this.nodes[j+1];
            this.nodes[j+1] = temp;
 
            this.nodes[j].x = 5 + j * 55;
            this.nodes[j+1].x = 5 + (j+1) * 55;
        }
    }
}
 
Colored by Color Scripter
cs

가장 큰 값을 뒤로 밀어낸다고 보시면 됩니다. 뒤에서 부터 정렬된 값이 쌓이기 때문에 3번째 줄의 for문은 length - 1 - i만큼만 돌게 됩니다. length - 1은 j와 j+1을 비교하기 때문에 넣어줍니다.