이번에는 반복적인 방법으로 해결하는 거품 정렬(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) – 교환
…생략…