[C 알고리즘] 버블 정렬- Bubble Sort Algorithm

앞서 배운 선택정렬은 제일 최솟값을 선택하여 앞으로 보내주는 과정을 반복하는것이었다.

 

이번에 배울 버블정렬의 핵심 아이디어는 옆에 있는 수와 비교해서 작은것을 앞으로 보내는 것이다.

 

1 10 5 8 7 6 4 3 2 9

1 10 5 8 7 6 4 3 2 9

1  5 10 8 7 6 4 3 2 9

1  5 8 10 7 6 4 3 2 9

1  5 8 7 10 6 4 3 2 9

 

위 과정을 반복하게 되면 

 

1  5 8 7 6 4 3 2 9 10

이 된다. 즉 한번의 싸이클로 시행하게되면 가장 큰수가 제일 뒤로 밀려나는 꼴이다.

 

이 같은 과정을 N번 반복해주므로 빅오표기법에 의한 시간복잡도는 O(N^2)이다.

 

1. N번 반복해주는 A라는 알고리즘정렬

2. A는 첫번째 인덱스부터 시작하여 그 옆의 인덱스와 대소관계를 비교하는 작업을 마지막 인덱스까지 한다

3. 반복 시행횟수가 늘어날때마다 마지막 인덱스가 한칸씩 줄어든다 . 

 

위 3가지를 바탕으로 하여 코드를 작성하겠습니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

#include <stdio.h> void swap(int* p, int a, int b); int main(void) {     int i, j, min, index, temp;     int array[10] = { 1, 10 , 5 , 8 ,7 ,6 ,4 ,3 ,2 ,9 };       for (int i = 0; i < 10; i++) {           for (int j = 0; j < 9 - i; j++) { /* array 인덱스가 9까지 있으므로 9를 접근해버리면                                  j+1 코드에서 배열크기밖의 원소를 침범*/               if (array[j] > array[j + 1]) {                 swap(array, j, j + 1);             }         }     }       for (int k = 0; k < 10; k++) {         printf("%d", array[k]);     }     return 0; }   void swap(int* p, int a, int b) {     int temp = 0;     temp = p[a];     p[a] = p[b];     p[b] = temp; }   Colored by Color Scripter

cs