정렬 - 버블 정렬 알고리즘

 

 

https://www.programiz.com/c-programming/online-compiler/

Online C Compiler

 

 

버블 정렬 알고리즘이란?

• 서로 인접한 두 원소끼리 비교를 하면서 정렬을 하는 알고리즘이다. 
• 2개의 레코드와 크기를 비교하면서 어느 한쪽이 더 작은 경우 큰 값과 서로 교환(Swap)을 한다. 

 

 

버블 정렬 동작 과정 직접 눈으로 확인하기

https://commons.wikimedia.org/wiki/File:Bubble-sort-example-300px.gif

보는 것처럼 사이클(회전)이 시작되면

1. 맨 앞의 두개의 요소끼리 서로 크기를 비교해서 더 작은 값을 왼쪽으로 이동(교환) 시킴.

2. 그 다음 빨간 박스를 +1 증가 시켜서 방금 비교한 큰 값과 바로 옆의 요소와 또 비교후 스왑

 

 

그러면 최종적으로 값이 가장 큰 8이 배열의 맨 끝쪽에 위치하게 된다. 

 

여기까지가 바로 1회전이고 이런 회전을 반복한다. 

 

주의사항

이미 리스트에서 가장 큰 값인 8이 맨 오른쪽에 위치해 있기 때문에 또 다시 빨간 박스를 굳이 맨 끝까지 가서 8과 비교할 필요가 없다는 것이다. 더 효율적으로 처리하기 위해서

한 사이클이 끝날 때마다 비교하는 횟수가 N-1씩 줄어들게 해주는게 중요하다.

 

5 3 1 6 7 2 4 8

3 1 5 6 2 4 7 8

1 3 5 2 4 6 7 8

...

1 2 3 4 5 6 7 8

 

저 빨간 숫자들은 더이상 비교할 필요가 없다는 의미이다. 

 

 

#include <stdio.h>

#define SWAP(a,b){int t; t=a; a=b; b=t;}

int main() {
    int numbers[] = { 9, 2, 5, 6, 8, 1, 4, 7, 3 };
    
    for(int i=sizeof( numbers )/4; i>0; i--){
    
        for( int j=0; j<i; j++ ){
            
            if( numbers[j] > numbers[j+1] ){
                printf("numbers[j]: %d | numbers[j+1]: %d\n", numbers[j], numbers[j+1]);
                SWAP( numbers[j], numbers[j+1]);
            }
            
        }
        
        printf("\n");
        
    }
    
    printf("결과: ");
    // 모두 출력
    for(int i=0; i<sizeof( numbers )/4; i++){
        printf("%d ", numbers[i]);
    }
    
    return 0;
}

 

[출력]

numbers[j]: 9 | numbers[j+1]: 2
numbers[j]: 9 | numbers[j+1]: 5
numbers[j]: 9 | numbers[j+1]: 6
numbers[j]: 9 | numbers[j+1]: 8
numbers[j]: 9 | numbers[j+1]: 1
numbers[j]: 9 | numbers[j+1]: 4
numbers[j]: 9 | numbers[j+1]: 7
numbers[j]: 9 | numbers[j+1]: 3

numbers[j]: 8 | numbers[j+1]: 1
numbers[j]: 8 | numbers[j+1]: 4
numbers[j]: 8 | numbers[j+1]: 7
numbers[j]: 8 | numbers[j+1]: 3

numbers[j]: 6 | numbers[j+1]: 1
numbers[j]: 6 | numbers[j+1]: 4
numbers[j]: 7 | numbers[j+1]: 3

numbers[j]: 5 | numbers[j+1]: 1
numbers[j]: 5 | numbers[j+1]: 4
numbers[j]: 6 | numbers[j+1]: 3

numbers[j]: 2 | numbers[j+1]: 1
numbers[j]: 5 | numbers[j+1]: 3

numbers[j]: 4 | numbers[j+1]: 3




결과: 1 2 3 4 5 6 7 8 9

 

소소하면서 쓸만한 팁

위의 소스처럼 

C언에서 간단히 SWAP 함수를 구현하고 싶다면 아래의 매크로 함수를 코드의 상단에 적어주기만 하면 된다. 

#define SWAP(a,b){int t; t=a; a=b; b=t;}

 

또한 배열의 크기를 알아내고 싶으면 sizeof 함수를 사용하면 유용하다. 

sizeof(arr) / 4
혹은
sizeof(arr) / sizeof(int)

sizeof는 변수의 사이즈를 가져와주는 함수이며, 배열안의 변수 개수 x 타입의 사이즈로 출력이 된다. 

여기서는 타입의 사이즈는 필요가 없으니 / sizeof(타입)을 적어준 것이다.