[자료구조] 17 버블정렬

📌버블 정렬 (Bubble Sort)

👉 항목의 키 값을 풍선에 비유한 것이다 버블!

값이 클수록 더 높이높이 올라간다 

가장 큰 값의 키가 오른쪽 끝으로 이동하고 그 다음 큰 값은 그 옆으로 그옆으로... 반복

 

📌시간복잡도 : O(n^2)

중복해서 비교가 일어난다

 

 

✔️ 알고리즘

1. 가장 왼 쪽의 인접한 두 수를 비교하여 왼쪽 수가 더 크면 오른쪽과 위치 변경

2. 오른쪽으로 1칸 이동.. 같은 방식으로 두 수 비교하면서 교확 

3. 가장 오른쪽에 도달할 때까지 반복

4. 오른쪽 끝에 최댓값이 도달하였으면 이 원소 제외하고 나머지 원소 반복

 

버블 정렬

 

5	1	4	3	8	swap = 0
1	5	4	3	8	1
1	4	5	3	8	1
1	4	3	5	8	1
1	4	3	5	8	1
1	4	3	5	8	0
1	3	4	5	8	1
1	3	4	5	8	0

👆버블 정렬 

 

#include <stdio.h>
void bubble_sort(int num[], int n);
void print_array(int num[], int n);

void main(){
    int num[] = { 5, 1, 4, 3, 8};
    bubble_sort(num, 5);
}

void print_array(int num[], int n){
    int i;
    for (i=0;i<n;i++){
        printf("%d ", num[i]);
    }
    printf("\n");
}

void bubble_sort(int num[], int n){
    int i,j,swap,temp;
    for (i=0; i<n-1; i++){
        swap =0;
        for (j=0; j<n-1; j++){
            if(num[j] > num[j+1]){
                temp = num[j];
                num[j] = num[j+1];
                num[j+1] = temp;
                swap = 1;
            }
        }
        if (swap == 0) break;
        print_array(num, n);
    }
}

// 1 4 3 5 8 
// 1 3 4 5 8