[C언어] 버블정렬

버블정렬 (bubble sort) 이란 2개 이상의 주어진 수들 중 인접한 두개의 수(레코드)를 비교하여  크거나 작은 순으로 정렬하는 것이다. 버블정렬은 구현이 매우 간단한 것에 비해 비경제적이다. 인접한 두 원소들을 하나하나 비교하여 정렬 하기 때문에 처리 시간(run-time)이 증가하고 더이상 비교를 할 필요가 없는 위치에 있음에도 불구하고 swap과정을 거쳐야 하기 때문에 불필요한 과정을 한번더 겪는다 이러한 방식때문에 다른 정렬 방식에

비하여 경제적이지 못하다는 특징이 있다

 

다음 정렬의 예시로 6, 4, 7, 9, 1을 버블정렬을 취했을때 5개의 수를 5 - 1 번 (4번)을 각각 매치하면서

비교해야 하므로 for배열을 이중으로 사용한다.  for(i=0; i<5; ++i){for(j=0; j<4; ++j){[비교]}}이때 [비교]에 들어갈

코드는 오름차순의 경우 작은 수 부터 큰 수대로 차례로 정렬하므로 인접한 수중 첫번째 수가 두번째 수보다 클 경우

swap이 일어나서 두수의 위치가 바뀌어야 한다. 이때 우리는 temp 변수를 이용하여 두수를 서로 교환한다. 그러므로 결과는 1 4 6 7 9 이다. 마찬가지로 내림차순의 경우 그 반대로 첫번째 수가 두번째 수 보다 작을 경우애 swap이 일어나도록 코드를 작성한다.

따라서 코드는 다음과 같다.

 

 

 

#include <stdio.h>

int main(){
   int arr[5] = {6, 4, 7, 9, 1};
   int i, j, k;
   int temp;

   for(i=0; i<5; ++i)
      printf("%3d", arr[i]);

   printf("\n");

   for(i=0; i<5; ++i){
      for(j=0; j<4; ++j){
         if(arr[j] > arr[j+1]){
            temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
         }
      }
   }
   for(i=0; i<5; ++i)
      printf("%3d", arr[i]);

   return 0;
}