버블 정렬(Bubble Sort) - C언어/자료구조

 

'보글보글 거품 같이 차례차례 정렬하는 버블정렬'

 

버블정렬은 거품정렬이나 버블소트(Bubble Sort)라고도 부릅니다.

 

 

버블정렬은 데이터 정렬을 하는 방법 중 하나입니다.

 첫 번째 자료와 두 번째 자료, 두 번째 자료와 세 번째 자료, 세번째와 네 번째 자료를

 비교하는 식으로 정렬을 진행합니다. (아래 그림 보시면 이해가 빠를 겁니다.)

 

 

여러 회전을 반복하여 정렬하는 방법입니다.

 

첫 번째 회전에서는

 첫 번째 자료와 두 번째 자료를 비교하여 첫 번째 자료가 더 큰 경우

 첫 번째와 두 번째 자료를 바꿉니다. (두 번째가 더 큰 경우는 안 바꿈 )

 그리고 두 번째 자료와 세 번째 자료를 비교하여 위와 같은 작업을 해줍니다.

 마찬가지로 세 번째와 네 번째, 그렇게 마지막 자료까지 비교해줍니다.

 (그렇다면 결과적으로 마지막 자리가 가장 큰 자료가 들어가겠죠?)

 

두 번째 회전에서는

 첫 번째와 마찬가지로 쭉 진행합니다.

 다만, 마지막 자리는 이미 가장 큰 수로 결정되어 있기 때문에

 마지막의 전 자리의 자료까지만 비교합니다. 비교 횟수가 한 번 줄겠죠?

 (그 결과로는 두 번째로 큰 자료(끝에서 두 번째)가 정해집니다.)

 

 

그렇게 모든 정렬이 끝날 때까지 반복합니다.

(스위치[검사]를 사용하면 자료가 미리 완료된 경우 그만 회전하도록 합니다.)

 

 

 

실제로 5개의 숫자 배열 자료가 어떻게 정렬되는지 확인해볼까요?

 

 

7, 4, 10, 3, 5 숫자를 가지고

버블소트(버블정렬) 하는 과정을 보도록 하겠습니다.

 

 

1 회전

가장 먼저 첫 번째 자리와 두 번째 자리의 자료를 비교합니다.

7과 4를 비교한 결과

4가 더 작기 때문에 서로 교환해줍니다.

 

 

다음으로 두 번째 자리와 세 번째 자리의 자료를 비교합니다.

7과 10을 비교한 결과

두 번째 자리의 7이 더 작기 때문에 교환하지 않습니다.

 

 

다음으로 세 번째 자리와 네 번째 자리의 자료를 비교합니다.

10과 3을 비교한 결과

세 번째 자리의 10보다 네 번째 자리의 3이 작기 때문에 교환합니다.

 

 

마지막으로 네 번째 자리와 다섯 번째 자리의 자료를 비교합니다.

10과 5를 비교한 결과

네 번째 자리의 10이 다섯 번째 자리의 5보다 크기 때문에

교환합니다.

 

(이렇게 첫 바퀴에서 가장 큰 숫자 10이 가장 오른쪽으로 간 것을 확인할 수 있습니다.)

 

 

2 회전

두 번째 회전에서 처음과 같이 첫 번째 자리와 두 번째 자리의 자료를 비교합니다.

4와 7을 비교한 결과

첫 번째 자리의 4가 더 작기 때문에 교환하지 않습니다.

 

 

다음으로 두 번째 자리와 세 번째 자리의 자료를 비교합니다.

7과 3을 비교한 결과

두 번째 자리의 7이 세 번째 자리의 3 보다 크기 때문에 교환해줍니다.

 

 

다음으로 세 번째 자리와 네 번째 자리의 자료를 비교합니다.

7과 5를 비교한 결과

세 번째 자리의 7이 네 번째 자리의 5보다 크기 때문에 교환해줍니다.

 

(이렇게 두 번째로 큰 수인 7, 가장 큰 수인 10이 정렬 완료되었습니다.)

 

 

3 회전

다시 처음으로 돌아와 첫 번째 자료와 두 번째 자료를 비교합니다.

4와 3을 비교한 결과

첫 번째의 4가 두 번째의 3보다 크기 때문에 서로 교환해줍니다

 

 

이번에는 두 번째 자료와 세 번째 자료를 비교합니다.

4와 5을 비교한 결과

두 번째의 4가 세 번째의 5보다 작기 때문에 그대로 둡니다.

 

(이렇게 세 번째로 큰 수인 5도 결정됐습니다.)

 

 

4 회전

마지막 회전입니다.

첫 번째 자리의 3과 두 번째 자리의 4를 비교한 결과

첫 번째 자리가 두 번째 자리보다 작기 때문에 그대로 둡니다.

 

(이렇게 네 번째로 큰 수인 4도 결정됐습니다.)

 

 

나머지 하나는 그대로 둬도 가장 작은 숫자이기 때문에

비교하지 않아도 맞는 위치임을 알 수 있습니다.

 

버블 정렬이 완료되었습니다.

 

 

 

 

 

 

 

그러면 이번에는 C 프로그램으로 확인해볼까요?

(소스 제공하지만 위의 과정을 보고 직접 만들어보면 좋습니다.)

 

 

출력 결과 예를 보고

프로그램 소스를 작성해보세요.

 

(출력 결과 예)

 

 

 

 

제가 완성한 소스입니다.

 

보고 참고하세요.

 

 

(복사할 수 있는 소스는 아래 전체복사용소스보기를 누르시면 됩니다.)

 

 

 

 

 

 

 

#include<stdio.h>
//Prosto
int main(void) {
 int data[10] = { 10, 6, 7, 9, 3, 4, 2, 1, 5, 8 };
 //int data[10] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
 int temp;
 //랜덤한 위치라고 생각.
 printf("정렬 전 순서\n"); //정렬하기 전 상태 출력.
 for (int i = 0; i < 10; i++) {
  printf("%d ", data[i]);
 }
 printf("\n");

 //아래의 2중 for문이 버블 정렬 핵심.
 for (int i = 1; i < 10; i++) { //1부터 9까지 9번 반복.
  for (int j = 0; j < 10-i; j++) { //배열 0번부터 10-i번까지(반복 횟수마다 감소)
   if (data[j] > data[j+1]) { //j와 j+1번 비교 작업(버블버블)
    temp = data[j]; //swap.
    data[j] = data[j+1];
    data[j+1] = temp;
   }
  }
 }

 printf("정렬 후 순서\n"); //정렬한 후 상태 출력.
 for (int i = 0; i < 10; i++) {
  printf("%d ", data[i]);
 }
 printf("\n");
 return 0;
}

 

 

 

추가적으로 스위치를 사용하는 경우 조건문으로 확인을 하지만,

중간에 정렬이 완료된 경우는 더 이상 버블 정렬을 진행하지 않고

정렬을 마칩니다.

 

 

위의 소스에서 사용하여 바꾼 소스는 아래와 같습니다.

 

 

 

#include<stdio.h>
//Prosto
int main(void) {
 int data[10] = { 10, 6, 7, 9, 3, 4, 2, 1, 5, 8 };
 //int data[10] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
 //int data[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
 int sw = 1;
 int temp;
 //랜덤한 위치라고 생각.
 printf("정렬 전 순서\n"); //정렬하기 전 상태 출력.
 for (int i = 0; i < 10; i++) {
  printf("%d ", data[i]);
 }
 printf("\n");

 //아래의 2중 for문이 버블 정렬 핵심.
 for (int i = 1; i < 10; i++) { //1부터 9까지 9번 반복.
  if (sw) {
   sw = 0;
   for (int j = 0; j < 10 - i; j++) { //배열 0번부터 10-i번까지(반복 횟수마다 감소)
    if (data[j] > data[j + 1]) { //j와 j+1번 비교 작업(버블버블)
     temp = data[j]; //swap.
     data[j] = data[j + 1];
     data[j + 1] = temp;
     sw = 1; //한번이라도 데이터 교환 발생하면 아직 교환 대상 남은 것으로 간주.
    }
   }
  }
  else { //sw(스위치) 0이면 종료.
   //printf("i = %d에서 끝남", i);
   break;
  }
 }

 printf("정렬 후 순서\n"); //정렬한 후 상태 출력.
 for (int i = 0; i < 10; i++) {
  printf("%d ", data[i]);
 }
 printf("\n");
 return 0;
}

 

 

 

 

 

궁금한 점 있으시면 댓글이나 따로 메일로 질문하시면 시간되는 대로 답변드리겠습니다. ( 연락 )