버블 정렬은 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복합니다.

// 버블 정렬
#include <stdio.h>
#include <stdlib.h>

#define swap(type, x, y) do { type temp = x; x = y; y = temp; } while (0)

// 버블 정렬 함수
void bubble_sort(int* arr, int n) {
  int k = 0;
  while (k < n - 1) {
    int last = n - 1; // 마지막으로 교환된 위치
    for (int i = n - 1; i > k; i--) {
      if (arr[i - 1] > arr[i]) {
        swap(int, arr[i - 1], arr[i]);
        last = i; // 마지막으로 교환된 위치 업데이트
      }
    }
    k = last; // 다음 반복을 위해 k 업데이트
  }
}

// 배열 출력 함수
void print_array(int* arr, int n) {
  for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
  }
  printf("\\n");
}

// 메인 함수
int main() {
  int i, nx;
  int* arr;

  puts("버블 정렬 예제입니다.");
  printf("배열의 크기를 입력하세요: ");
  scanf("%d", &nx);
  // arr = (int *)malloc(nx * sizeof(int));
  // arr = malloc(nx * sizeof(int));
  arr = calloc(nx, sizeof(int)); // 메모리 할당 및 초기화
  /* 위 세 메모리 할당의 차이:
    1. (int *)malloc(nx * sizeof(int))는 메모리를 할당하지만 초기화하지 않습니다.
    2. malloc(nx * sizeof(int))는 C에서 타입 캐스팅 없이 메모리를 할당합니다.
       C에서는 malloc이 void 포인터를 반환하기 때문에 타입 캐스팅이 필요하지 않습니다.
       그러나 C++에서는 타입 캐스팅이 필요합니다.
    3. calloc(nx, sizeof(int))는 메모리를 할당하고 모든 바이트를 0으로 초기화합니다.
       따라서 calloc을 사용하면 배열의 모든 원소가 0으로 초기화됩니다.
  */

  if (arr == NULL) {
    fprintf(stderr, "메모리 할당 실패\\n");  // fprintf: 표준 오류 스트림에 출력
    /* fprintf vs printf:
       - fprintf는 파일 스트림에 출력할 수 있는 반면, printf는 표준 출력(stdout)에만 출력합니다.
       - fprintf를 사용하면 오류 메시지를 표준 오류(stderr)로 출력할 수 있습니다.
       - fprintf는 다양한 파일 스트림에 출력할 수 있어 유연성이 높습니다.
    */
    return 1;
  }
  printf("배열의 원소를 입력하세요: ");
  for (i = 0; i < nx; i++) {
    printf("arr[%d]: ", i);
    scanf("%d", &arr[i]);
  }
  printf("원본 배열: ");
  print_array(arr, nx);
  bubble_sort(arr, nx);
  printf("정렬된 배열: ");
  print_array(arr, nx);
  free(arr); // 메모리 해제
  return 0;
  // return 0; // main 함수의 반환값은 0이므로 생략
  // return 0;는 프로그램이 성공적으로 종료되었음을 나타냅니다.
  // return 0;는 C 표준에 따라 main 함수의 반환값으로 사용됩니다.
  // C 표준에 따르면, main 함수는 int 타입을 반환해야 하며
  // 0을 반환하면 프로그램이 성공적으로 종료되었음을 나타냅니다.
  // return 0;는 C 프로그램의 관례로, main 함수가 성공적으로
  // 실행되었음을 나타내는 것입니다.
}

// 컴파일: gcc -o buble buble.c
// 실행: ./buble
// 출력:
// 원본 배열: 64 34 25 12 22 11 90
// 정렬된 배열: 11 12 22 25 34 64 90
// 시간 복잡도: O(n^2)
// 공간 복잡도: O(1)
// 이 코드는 C17 표준을 사용하여 작성되었습니다.
// 이 코드는 버블 정렬 알고리즘을 구현한 예제입니다.
// 버블 정렬은 인접한 두 원소를 비교하여 정렬하는 간단한 정렬 알고리즘입니다.
// 이 코드는 배열을 오름차순으로 정렬합니다.
// swap 매크로를 사용하여 두 원소의 값을 교환합니다.
// 버블 정렬은 최악의 경우 O(n^2)의 시간 복잡도를 가지며, 최선의 경우 O(n)의 시간 복잡도를 가집니다.
// 이 코드는 배열의 크기가 작을 때 유용합니다.
// 버블 정렬은 안정 정렬 알고리즘입니다.