[알고리즘] 버블정렬(Bubble sort)

알고리즘

 

버블정렬(Bubble sort)

 

간단 요약

 

가정) Array[5]= { 15 ,11 ,1 ,3 ,8 } 을 오름차순으로 정렬한다.

특징) 선택정렬은 앞에서 부터 작은수를 정렬시키지만 버블정렬은 뒤에서 부터 큰수를 정렬시킨다.

 

1.  첫번째 데이터 15와 두번째 데이터 11을 비교한다.

 

2.  15가 더 크기 때문에 서로 자리를 바꿔준다.

 

3.  다시 한칸 앞으로 이동해서 두번째 15 와 1을 비교한다.

(2번에서 15가 두번째 데이터로 이동한상태)

 

4. 이번에도 15가 더 크기 때문에 서로 자리를 바꾼다.

(현재 상태 { 11, 1, 15, 3, 8 } )

 

5. 1회차가 끝나면 { 11, 1, 3, 8, 15 } 형태가 되고 최대값이 마지막 배열에 위치한다.

 

6. n 번 반복

 

상세 설명

 

가정) Array[5]= { 15 ,11 ,1 ,3 ,8 } 을 오름차순으로 정렬한다.

 

 

 

 

 가장 먼저 첫번째와 두번째 데이터를 비교한다.

 

15 > 11 이므로 15를 앞으로 보내준다.

 

 

 

 

 다시 15와 다음 인덱스인 1을 비교한다.

이번에도 15 > 1 이므로 앞으로 보내준다.

 

 

 

다시 15와 3을 비교한다.

15 > 3 이므로 15를 앞으로 보내준다.

 

 

 

 

 

마지막으로 15 와 8을 비교한다.

15 > 8 이므로 15를 앞으로 보내준다.

이렇게 되면 최댓값이 마지막 인덱스에 저장된다.

 

 

 

 

이때, 마지막 인덱스는 고정하고

다시 처음부터 큰수를 앞으로 보내는 작업을 반복한다.

이하 설명은 생략

 

 

 

 

지금 같은 경우 2회차 만에 정렬이 완성되었다.

하지만

버블정렬은 2중 for문에 의해서 무조건

n(n-1) / 2 번의 비교과정을 거친다.

이 부분에서 시간복잡도의 효율성이 크게 떨어진다.

 

 

 

시간복잡도

 

 

 

 

 

코드

 

#include <stdio.h>
 
void swap(int* a, int* b) //스왑핑
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
 
int main(void) {
 
    int i, j;
    int arr[5] = { 15, 11, 1, 3, 8 };
 
    for (int z = 4; z >= 1; z--) { // 마지막 위치를 하나씩 앞당김
 
        for (i = 0; i < z; i++) { // 비교1 
 
            j = i + 1; //비교 2
            if (arr[i] > arr[j]) {  // 비교1이 비교2보다 크면 스왑핑
                swap(&arr[i], &arr[j]);
            }
        }
    }
    for (int k = 0; k < 5; k++)
    {
        printf("%d", arr[k]);
    }
    return 0;
}

 

 

 

출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

출처 : https://terms.naver.com/entry.nhn?docId=2270437&cid=51173&categoryId=51173