버블정렬
이웃하는 숫자를 비교하여 작은 수를 앞 쪽으로 이동시키는 과정을 반복하여 정렬하는 알고리즘이다.
버블정렬의 시간복잡도는 O(N^2)이다.
한 번의 Loop에 요소의 갯수만큼 비교를 하며 총 Loop는 요소의 개수번 돈다.
정렬할 수:
15, 2, 6, 27, 24, 9, 8, 13,10, 1, 5
실행 결과
0 회전 결과: 2 6 15 24 9 8 13 10 1 5
1 회전 결과: 2 6 15 9 8 13 10 1 5 24
2 회전 결과: 2 6 9 8 13 10 1 5 15 24
3 회전 결과: 2 6 8 9 10 1 5 13 15 24
4 회전 결과: 2 6 8 9 1 5 10 13 15 24
5 회전 결과: 2 6 8 1 5 9 10 13 15 24
6 회전 결과: 2 6 1 5 8 9 10 13 15 24
7 회전 결과: 2 1 5 6 8 9 10 13 15 24
8 회전 결과: 1 2 5 6 8 9 10 13 15 24
9 회전 결과: 1 2 5 6 8 9 10 13 15 24
10 회전 결과: 1 2 5 6 8 9 10 13 15 24
11 회전 결과: 1 2 5 6 8 9 10 13 15 24
소스코드:
void bubblesort(int a[], int n){
for(int k = 0; k <= n; k++){ //k는 0부터 n(요소 개수)까지
for (int i = 0; i < n - k; i++) { //i는 0부터 요소개수 - k까지 1)
if (a[i + 1] < a[i]) {
int tmp = a[i + 1];
a[i + 1] = a[i];
a[i] = tmp;
}
}
}
}
1) i가 n - k까지인 이유는 Loop가 1회전 할 때마다 큰 수 부터 뒤에서 정렬되기 때문
0 회전 결과: 2 6 15 24 9 8 13 10 1 5
1 회전 결과: 2 6 15 9 8 13 10 1 5 24
2 회전 결과: 2 6 9 8 13 10 1 5 15 24
1회전 결과로 까장 큰 수 24 가 정렬됨 (11 - 1 = 10 ) 10번째 위치 정렬 완료.
2 회전 결과: 2 6 9 8 13 10 1 5 15 24
2회전 결과로 11 - 2 = 9 9번째 위치 정렬 완료