[자료구조] 버블소트

#include <stdio.h>

void bubble(int a[], int len){
int i;
int j;
int temp;

for (i = 0; i < len - 1; i++){
for (j = 0; j<(len - i) - 1; j++){
if (a[j] > a[j + 1]){
temp = a[j];
a[j] = a[j + 1];
a[j+1] = temp;
}
}
}
}

int main(){
int a[] = { 3, 2, 4, 1 };
int i;
bubble(a, sizeof(a) / sizeof(int));

for (i = 0; i < 4; i++){
printf("%d ", a[i]);
}
return 0;
}

- 버블 소트의 핵심은 i와 j의 변형이다.
3241이 정렬되는 과정

i j
0 0 [32]41 -> 2341
0 1 2[34]1 -> 2341
0 2 23[41] -> 2314
1 0 [23]14 -> 2314
1 1 2[31]4 -> 2134
2 0 [21]34 -> 1234
배열의 길이 len = 4

i는 0부터 2까지 순차적으로 증가하며 j값을 줄여준다.
j가 i=1 비교일때 3번, i=2 비교일때 2번, i=3 비교일때 1번씩 줄어든다.
고로 비교횟수는 j이고 j는 총 3회 실시하므로 i는 3이된다.
시간 복잡도 - O(n^2)