1-2) [C] 버블정렬(Bubble Sort)

1) 버블정렬이란?

오른쪽부터 왼쪽 방향으로 인접한 두 개의 숫자를 비교해서 교환

오른쪽부터 왼쪽으로 숫자를 옮겨가는 모양이 물속에서 거품이 올라오는 모양과 비슷하다고 해서 버블이라고 함

 

1. 수열의 오른쪽 끝의 두 숫자를 비교해서 더 작은 수를 왼쪽으로 보낸다.

2. 왼쪽으로 한 칸 이동하여 같은 방법으로 숫자를 비교한다.

3. 가장 작은 숫자가 왼쪽 끝으로 이동했으므로 왼쪽 끝은 정렬을 끝냈다고 간주

4. 다시 가장 오른쪽부터 같은 과정 반복

5. 왼쪽 숫자가 더 작을 경우 숫자는 바꾸지 않고 화살표만 왼쪽으로 한 칸 이동

6. 반복 

7. 반복

8. 정렬 완료

2) 버블정렬의 시간복잡도

버블 정렬은 선형 탐색을 위해 1라운드에서 n-1, 2라운드에서 n-2, ... , n-1라운드에서 1회 비교를 한다.

따라서 비교 횟수는 (n-1) + (n-2) + ... + 1 ≈  n^/2가 된다. 비교 횟수는 입력 데이터의 순서와 상관없이 일정하다.

 

또한, 숫자 교체횟수는 입력 데이터에 의존한다. 입력 데이터가 작은 순으로 나열되어 있다면 교체는 발생하지 않는다. 하지만 큰 데이터가 큰 순으로 나열되어 있다면 비교할 때마다 교체해야한다.

따라서 선택 정렬의 계산 시간은 O(n^2)이다.

 

3) 버블정렬 구현

- Left.ver - 진행순서(data[0]부터 비교시작해서 큰 수 먼저 정렬)

#include <stdio.h>

int main(void){
  int data[6] = {5, 2, 4, 6, 3, 1};
  int temp;
  printf("Before sorting :\n");
  for(int i =0; i<6;i++){
    printf("%d",data[i]);
  }
  printf("\n");
  for(int i=1; i<6;i++){ 
      for(int j=0;j<6-i;j++){ 
          if(data[j]>data[j+1]){ 
              temp=data[j];
              data[j]=data[j+1];
              data[j+1]=temp; 
          }
      }
  }
  printf("After sorting :\n");
  for(int i=0; i<6;i++){
      printf("%d",data[i]);
  }
  printf("\n");
  return 0;
  }

결과화면

Before sorting :
524631
After sorting :
123456

 

중간점검화면

 

Before sorting :
524631
1번째 :245316
2번째 :243156
3번째 :231456
4번째 :213456
5번째 :123456
After sorting :
123456

- Right.ver - 진행순서(data[5]부터 비교시작해서 작은 수 먼저 정렬) 

#include <stdio.h>

int main(void){
  int data[6] = {5, 2, 4, 6, 3, 1};
  int temp;
  printf("Before sorting :\n");
  for(int i =0; i<6;i++){
    printf("%d",data[i]);
  }
  
  for(int i=5; i>0;i--){ // 
      for(int j=4;j>=0;j--){ //
          if(data[j]>data[j+1]){ //
              temp=data[j];
              data[j]=data[j+1];
              data[j+1]=temp; //
            } 
        } //반복횟수에 따른 정렬상태 확인용 출력코드 추가
        printf("\n%d번째 :",i);
        for(int i=0; i<6;i++){
      printf("%d",data[i]);
  }
  
    }
  printf("\nAfter sorting :\n");
  for(int i=0; i<6;i++){
      printf("%d",data[i]);
  }
  
  return 0;
  }

 

결과화면(왼쪽부터 정렬 완료)

Before sorting :
524631
5번째 :152463
4번째 :125346
3번째 :123546
2번째 :123456
1번째 :123456
After sorting :
123456