[알고리즘] 버블 정렬(Bubble Sort) 알고리즘 개념과 원리에 대해 쉽고 빠르게 공부해보자 [C언어]

버블 정렬(Bubble Sort) 알고리즘의 개념

- 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘

   > 인접한 2개의 값을 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.

- 선택 정렬과 기본 개념이 유사하다.

 

 

버블 정렬 알고리즘의 동작 원리

- 버블 정렬은 첫 번째 값과 두 번째 값을, 두 번째 값과 세 번째 값을 ... 마지막( - 1)값과 마지막 값을 비교하여 자료를 정렬하는 알고리즘이다.

- 처음 돌고나면 제일 큰값이 맨 뒤로 이동하게 되며, 2번째돌면 2번째로 큰값이 마지막 - 1 값 위치에 정렬되고 이를 N의 값만큼 전부 수행하게 된다.

 

 

이미지로 보는 동작 절차

1) 1번 값과 2번 값을 비교 후 1번 값이 크다면 1번 값과 2번 값의 자리를 바꾼다. 

2) 2번 값과 3번 값을 비교 후 2번 값이 3번 값보다 크다면 자리를 바꾸지만, 2단계에서는 3번 값이 자리가 크기에 그대로 둔다.

3) 3번 값과 4번 값을 비교하고 3번 값이 4번 값보다 크다면 바꾸고 그렇지 않다면 그대로 둔다.

4) 숫자의 비교를 N - 1 번 값 과 N 값까지 비교를 하면 첫번째 순회가 종료된다.  

5) 6단계에서 확인이 가능하듯 제일 큰 숫자가 맨뒤에 자리잡게 된다.

 

 

 

6) 1차 스캔이 완료 된 후 2차, 3차 ... 계속적으로 진행해서 아래 이미지에 [정렬 완료]부분 같이 모든 정렬이 끝나게 된다.

 

 

 

 

버블 정렬 C언어 코드

#include <stdio.h>
 
int main(void) {
    int i, j, temp;
    int arr[10] = {10, 1, 5, 8, 7, 6, 4, 3, 2, 9};
    for(i = 0; i < 10; i++) {
        for(j = 0; j < 9 - i; j++) {
            if(arr[j] > arr[j+1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }    
        }
    }
    for(i = 0; i < 10; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

 

결과

 

 

 

버블 정렬 알고리즘 특징

장점

- 인접한 값만 계쏙해서 비교하는 방식으로 구현이 쉬우며, 직관적이다.

- n개 원소에 대해 n개의 메모리를 사용하기에 데이터를 하나씩 정밀 비교를 한다.

 

단점 

- 최선이든 최악이든 O(N^2)의 시간복잡도를 가진다.

- n개 원소에 대해 n개의 메모리를 사용하기에 원소의 개수가 많아지는 만큼 비교 회수가 많아져 성능이 저하된다.

 

 

 

 

 

베타존 : 네이버쇼핑 스마트스토어