Algorithm(4): Bubble Sort

버블 정렬

#define MAX 100

void print_array(const int arr[], int length);
void swap(int*, int*);
void bubble_sort(int arr[], int length);

int main() {
  int i = 0, temp, data[MAX];
  printf("Enter integers seperated by a blank.\n");
  while (1) {
    scanf("%d", &temp);
    if (temp < 0)
      break;
    data[i++] = temp;
  }

  printf("Before sorting: ");
  print_array(data, i);
  printf("\n");

  bubble_sort(data, i);
  printf("After sorting: ");
  print_array(data, i);
  printf("\n");

  return 0;
}

void print_array(const int arr[], int length)
{
  int i;
  for (i = 0; i<length; i++)
    printf("%d ", arr[i]);
}

void swap(int *p, int *q)
{
  int temp;
  temp = *p;
  *p = *q;
  *q = temp;
}

void bubble_sort(int arr[], int length)
{
  int pass, current;

  for (pass = 1; pass < length; pass++)
  {
    for (current = 0 ;current < (length - pass) ;current++)
    {
      if (arr[current] > arr[current+1])
      {
        swap(&arr[current], &arr[current+1]);
      }
    }
  }
}

분석

프로그램의 주요 기능
사용자 입력:

정수를 입력받아 배열 data에 저장합니다.
음수를 입력하면 입력이 종료됩니다.
정렬 전 배열 출력:

함수 print_array를 호출하여 배열을 출력합니다.
버블 정렬 수행:

함수 bubble_sort를 호출하여 배열을 정렬합니다.
정렬 후 배열 출력:

다시 print_array를 호출하여 정렬된 배열을 출력합니다.

핵심 아이디어:
배열을 반복 순회하며, 인접한 두 원소를 비교합니다.
만약 왼쪽 값이 오른쪽 값보다 크다면 자리 교환(swap) 을 수행합니다.
한 번의 패스(pass) 후에는 가장 큰 값이 배열의 마지막에 위치합니다.

정렬과정

동작 단계
배열이 [3, 1, 4, 1, 5]라고 가정하고 정렬 과정을 보겠습니다.

첫 번째 패스 (pass = 1):
배열 [3, 1, 4, 1, 5]를 순회하며 인접한 두 값을 비교하고 교환합니다.

비교: 3 > 1 → 교환 → [1, 3, 4, 1, 5]
비교: 3 > 4 → 교환 없음.
비교: 4 > 1 → 교환 → [1, 3, 1, 4, 5]
비교: 4 > 5 → 교환 없음.
결과: [1, 3, 1, 4, 5] (가장 큰 값 5가 배열의 끝에 위치).

두 번째 패스 (pass = 2):
배열 [1, 3, 1, 4]를 순회하며 비교합니다(마지막 값은 이미 정렬).

비교: 1 > 3 → 교환 없음.
비교: 3 > 1 → 교환 → [1, 1, 3, 4, 5]
비교: 3 > 4 → 교환 없음.
결과: [1, 1, 3, 4, 5].

세 번째 패스 (pass = 3):
배열 [1, 1, 3]를 순회하며 비교합니다.

비교: 1 > 1 → 교환 없음.
비교: 1 > 3 → 교환 없음.
결과: [1, 1, 3, 4, 5].

네 번째 패스 (pass = 4):
배열 [1, 1]를 비교합니다.

비교: 1 > 1 → 교환 없음.
결과: [1, 1, 3, 4, 5] (이미 정렬 완료).

최종 결과
입력: [3, 1, 4, 1, 5]
출력: [1, 1, 3, 4, 5].

시간복잡도

• 최악의 경우: O(n^2) , 중첩 루프 때문

버블 정렬 최적화 버전

이미 정렬이 되어 있는지 확인

#define MAX 100

void print_array(const int arr[], int length);
void swap(int*, int*);
void bubble_sort(int arr[], int length);

int main() {
  int i = 0, temp, data[MAX];
  printf("Enter integers seperated by a blank.\n");
  while (1) {
    scanf("%d", &temp);
    if (temp < 0)
      break;
    data[i++] = temp;
  }

  printf("Before sorting: ");
  print_array(data, i);
  printf("\n");

  bubble_sort(data, i);
  printf("After sorting: ");
  print_array(data, i);
  printf("\n");

  return 0;
}

void print_array(const int arr[], int length) {
  int i;
  for (i = 0; i < length; i++)
    printf("%d ", arr[i]);
}

void swap(int* p, int* q) {
  int temp;
  temp = *p;
  *p = *q;
  *q = temp;
}

void bubble_sort(int arr[], int length)
{
  int pass, current, sorted = 0; //이미 정렬 되어 있는지 확인
  for (pass = 1; (pass<length) && (!sorted); pass++)
  {
    sorted = 1;
    for (current = 0; current < (length  - pass) ; current++)
    {
      if (arr[current] > arr[current+1])
      {
        swap(&arr[current], &arr[current+1]);
        sorted = 0;
      }
    }
  }
}

정렬 되어 있는 경우 정렬을 하지 않을 수 있지만 시간복잡도는 동일하다.

선택정렬과 비교

선택 정렬과 비교했을 때 정렬되어 있는 경우를 뺄 수 있어서 효과적이다.