버블 정렬 (Bubble Sort)

버블 정렬은 인접한 두 요소를 비교하여 정렬하는 알고리즘으로, 작은 값은 앞으로, 큰 값은 뒤로 보내는 과정을 반복하며 거품이 올라오는 것처럼 정렬됩니다.

특징

• 정렬 방식: 비교 기반 정렬 알고리즘
• 시간 복잡도:
  • 최악: O(n²)
  • 최선: O(n) (이미 정렬된 경우)
• 공간 복잡도: O(1) (제자리 정렬)

작동 방식

1. 첫 번째 요소와 두 번째 요소를 비교
   • 두 요소의 크기를 비교하여, 순서가 잘못되었으면 위치를 교환.
2. 배열 끝까지 반복
   • 배열의 끝까지 인접한 두 요소를 비교하며 정렬.
3. 가장 큰 값 위치 확정
   • 한 번의 반복이 끝나면, 가장 큰 값이 배열의 끝에 위치.
4. 작업 반복
   • 배열 크기만큼 반복하여 전체 정렬을 완료.

#include <stdio.h>

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}