c언어 버블정렬(버블소트)

버블소트, 버블정렬은 같은 말입니다..sort(정렬)

3 2 4 1

이렇게 4개의 숫자를 버블정렬로 오름차순 정렬하면...

- 3과 2를 비교 하여 앞자리인 3이 크므로 두 수의 위치를 바꾼다.. (2 3 4 1)

- 3과 4를 비교하여 뒷자리인 4가 크므로 그냥 다음 단계로..(2 3 4 1)

- 4 와 1을 비교하여 앞자리인 4가 크므로 두 수의 위치를 바꾼다..(2 3 1 4)

-- 다시 처음으로 돌아와 2와 3을 비교 한다. 뒷자리 숫자가 더 크므로 다음단계로..(2 3 1 4)

-- 3과 1을 비교 앞자리 숫자가 더 크므로 교체(2 1 3 4)

(--)3과 4를 비교(***부분 참조) 뒷 자리의 수 4가 더 큼.(첫 바퀴에 이미 가장 큰 수를 맨 뒤에...)(2 1 3 4)

***( 소스를 작성하기에 따라 여기서 또 한 숫자를 마감 시켜버릴 수 도 있고. 의미 없긴 하나 3과 4를 비교 할 수도 있음. 하이픈이 하나인 위 3줄이 한 바퀴라고 가정할 때, 그때 이미 가장 큰 수를 맨 뒷자리에 가져다 놓았습니다. 그러므로 3 과 4는 반드시 비교 하여야 하는 것은 아닙니다. 이런 상황에서 3과 4를 비교하지 않는 알고리즘이 더 효율적임)***

---다시 처음으로 와서 2와 1을 비교 앞자리가 더 크므로 자리 교체.(1 2 3 4)

(---) 2 와 3을 비교, 뒷 자리 수가 더 크므로 교체 없음(1 2 3 4)

(---) 3과 4를 비교, 뒷 자리 수가 더 크므로 교체 없음(1 2 3 4)

***(여기서도 이미 뒤는 정렬이 끝난 상태입니다. 그러므로 여기서 그냥 끝내도 무관합니다. (---)기호가 앞에 붙은 줄은 역시 생략되어도 무관하며, 생략된 알고리즘이 더 효율적이라 할 수 있습니다.)***

 

@ 버블정렬은 한 바퀴 돌 때 마다 가장 큰 수를 맨 뒤로 밀어내는 형식으로 정렬이 됩니다.(내림차순은 반대: 가장 작은 수를 맨 뒤로)

@ 오름차순

#include <stdio.h> #define DATA 4 int main() {     int num[]={3,2,4,1};//초기값     int i, j , temp;          printf("초기 값 : ");     for(i=0;i<DATA;i++)         printf("%d ",num[i]);         printf("\n");                 for(i=0;i<DATA-1;i++)//비교횟수는 데이터갯수-1, 자기 자신과는 비교 하지 않음     {         for(j=0;j<DATA-1;j++)         {             if(num[j] > num[j+1])             {                 temp=num[j];//뒷자리의 수가 더 크면 교체                 num[j]=num[j+1];                 num[j+1]=temp;             }         }     }       printf("정렬 후 : ");     for(i=0;i<DATA;i++)         printf("%d ",num[i]);         printf("\n");      }

이 소스는 위 설명에서 (--), (---)으로 표현된 부분까지 작업하는 소스입니다. 생략되어도 될 부분까지도 작업해버리는 약간 비효율 적인 소스지 이지요...

 

@ 내림차순

#include <stdio.h> #define DATA 4 int main() {     int num[]={3,2,4,1};//초기값     int i, j , temp;          printf("초기 값 : ");     for(i=0;i<DATA;i++)         printf("%d ",num[i]);         printf("\n");                 for(i=0;i<DATA-1;i++)//비교횟수는 데이터갯수-1, 자기 자신과는 비교 하지 않음     {         for(j=0;j<DATA-1;j++)         {             if(num[j] < num[j+1])             {                 temp=num[j];//뒷자리의 수가 더 크면 교체                 num[j]=num[j+1];                 num[j+1]=temp;             }         }     }       printf("정렬 후 : ");     for(i=0;i<DATA;i++)         printf("%d ",num[i]);         printf("\n");      }

내림차순으로 변경되었습니다. 소스의 어느 부분이 변경되었을까요? 딱 문자 하나만 수정했습니다. 맞춰보세요...

 

@ 조금 더 효율적인 소스.(오름차순)

#include <stdio.h> #define DATA 4 int main() {     int num[]={3,2,4,1};//초기값     int i, j , temp,cnt=0;          printf("초기 값 : ");     for(i=0;i<DATA;i++)         printf("%d ",num[i]);         printf("\n");                 for(i=DATA-1;i>0;i--)//비교횟수는 데이터갯수-1, 자기 자신과는 비교 하지 않음     {         for(j=0;j<i;j++)         {             if(num[j] > num[j+1])             {                 temp=num[j];//뒷자리의 수가 더 크면 교체                 num[j]=num[j+1];                 num[j+1]=temp;             }             cnt++;         }     }       printf("정렬 후 : ");     for(i=0;i<DATA;i++)         printf("%d ",num[i]);         printf("\n");              printf("비교횟수 : %d 회\n", cnt); }

위 소스를 돌리면 비교횟수가 6회 입니다. (--), (---)를 붙여 설명했던 부분은 제외되기 때문입니다. 만약 첫 번째 오름차순 소스를 비교횟수 문장을 넣어보면 어떨까요? 소스는 생략하고 결과만 올릴게요.   9회 네요.. -,--,(--),---,(---)를 붙여 설명한 모든 상황에서 비교가 일어 납니다.

 

 

소스를 작성하기에 따라 이거보다 더 효율적인 소스도 있을 겁니다.

한번 연구해보세요.

[Computer/Programing] - c언어 삽입정렬

[Computer/Programing] - c언어 선택정렬