2.2 거품 정렬(Bubble Sort)

이번에는 반복적인 방법으로 해결하는 거품 정렬(Bubble Sort) 알고리즘을 살펴볼게요.

거품 정렬은 앞에서부터 이웃하는 원소의 값을 비교하여 위치를 교환하는 것을 반복해요. 이를 끝까지 수행하면 제일 큰 값이 맨 뒤에 위치합니다. 그리고 정렬할 개수를 1 줄인 후에 다시 반복해요. 정렬할 개수가 1일 때까지 반복하면 정렬 작업이 끝나요.

거품 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)

반복(i:=n->1)

반복(j:=1->i)

조건(compare(base[j-1], base[j]) > 0)

교환(base[j-1],base[j])

예:

2 9 4 1 5 6 8 3 7       (정렬 전, n:9)

2 9 4 1 5 6 8 3 7       (i:9, j:1)

2 9 4 1 5 6 8 3 7       (i:9, j:2)

2 4 9 1 5 6 8 3 7       (i:9, j:2) – 교환

2 4 9 1 5 6 8 3 7       (i:9, j:3)

2 4 1 9 5 6 8 3 7       (i:9, j:3) – 교환

2 4 1 9 5 6 8 3 7       (i:9, j:4)

2 4 1 5 9 6 8 3 7       (i:9, j:4) – 교환

2 4 1 5 9 6 8 3 7       (i:9, j:5)

2 4 1 5 6 9 8 3 7       (i:9, j:5) – 교환

2 4 1 5 6 9 8 3 7       (i:9, j:6)

2 4 1 5 6 8 9 3 7       (i:9, j:6) – 교환

2 4 1 5 6 8 9 3 7       (i:9, j:7)

2 4 1 5 6 8 3 9 7       (i:9, j:7) – 교환

2 4 1 5 6 8 3 9 7       (i:9, j:8)

2 4 1 5 6 8 3 7 9       (i:9, j:8) – 교환, 1회전 완료

2 4 1 5 6 8 3 7 9       (i:8, j:1)

2 4 1 5 6 8 3 7 9       (i:8, j:2)

2 1 4 5 6 8 3 7 9       (i:8, j:2) – 교환

2 1 4 5 6 8 3 7 9       (i:8, j:3)

2 1 4 5 6 8 3 7 9       (i:8, j:4)

2 1 4 5 6 8 3 7 9       (i:8, j:5)

2 1 4 5 6 8 3 7 9       (i:8, j:6)

2 1 4 5 6 3 8 7 9       (i:8, j:6) – 교환

2 1 4 5 6 3 8 7 9       (i:8, j:7)

2 1 4 5 6 3 7 8 9       (i:8, j:7) – 교환, 2회전 완료

2 1 4 5 6 3 7 8 9       (i:7, j:1)

1 2 4 5 6 3 7 8 9       (i:7, j:1) – 교환

…생략…