버블정렬(bubble sort)

버블정렬(bubble sort) : 이웃간의 정렬

---

인접한 인덱스의 원소끼리 비교,교환 방식 ⇒ 뒤에서부터 정렬

pseudocode

버블정렬(base : 배열시작주소 , n : 배열요소 개수)
	반복(i : 0 -> n)
		반복(j : 0 -> n-(i+1))
			조건(base[j] > base[j+1])
				교환(base[j],base[j+1])

best case 시간복잡도 : $O(n^2)$

worst case 시간복잡도 : $O(n^2)$

안정성 : 안정

장점 : 안정정렬

단점 : 많은 교환

실제코드

#include <stdio.h>

int main(int argc, const char * argv[]) {
    int arr[20] = {
        3,5,2,2,4,
        6,1,3,7,8,
        2,11,2,21,20,
        12,14,1,6,16};
    
    int i,j;
    int count;
    int n = sizeof(arr)/sizeof(int);
    for(i = 0 ; i < n ; i++){
        for(j = 0 ; j < n-1 ; j++){
            if(arr[j]>arr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                count++;
            }
        }
    }
    
    
    for (int k = 0 ; k < n ; k++){
        printf("%d ",arr[k]);
    }
    
    printf("\nn^%d",count/n);
    return 0;
}