A simple comparison-based sorting algorithm – O(n²)
Click tabs to switch between C and Python implementations
#include <stdio.h> /* ── 버블 정렬 함수 ── */ void bubbleSort(int arr[], int n) { int i, j; int temp; int swapped; for (i = 0; i < n - 1; i++) { swapped = 0; /* 패스마다 교환 여부 리셋 */ for (j = 0; j < n - i - 1; j++) { /* 현재값이 다음값보다 크면 교환 */ if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; swapped = 1; } } /* 한 패스 전체에서 교환이 없으면 이미 정렬됨 → 종료 */ if (swapped == 0) break; } } /* ── 배열 출력 유틸리티 ── */ void printArray(int arr[], int n) { int i; for (i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); } /* ── main ── */ int main(void) { int arr[] = { 45, 23, 78, 12, 67, 34, 89 }; int n = sizeof(arr) / sizeof(arr[0]); printf("Before : "); printArray(arr, n); bubbleSort(arr, n); printf("After : "); printArray(arr, n); return 0; }
# ── 버블 정렬 함수 ── def bubble_sort(arr): n = len(arr) for i in range(n - 1): swapped = False # 패스마다 교환 여부 리셋 for j in range(n - i - 1): # 현재값이 다음값보다 크면 교환 if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] swapped = True # 한 패스 전체에서 교환이 없으면 이미 정렬됨 → 종료 if not swapped: break # ── 메인 실행 ── if __name__ == "__main__": arr = [45, 23, 78, 12, 67, 34, 89] print("Before :", arr) bubble_sort(arr) print("After :", arr)
Bubble Sort iterates through an array, comparing adjacent elements one by one. If two neighbors are in the wrong order, it swaps them. The name comes from the idea that the largest value "bubbles up" to the end of the array with each pass.
A single full iteration is called a Pass. After Pass 1, the largest element is guaranteed to be in its final position at the end. Each subsequent pass locks one more element into place from right to left.
Example: Sort [5, 3, 8, 1, 2] in ascending order.
Pass 1 — Compare neighbors left to right:
• 5 vs 3 → swap → [3, 5, 8, 1, 2]
• 5 vs 8 → keep → [3, 5, 8, 1, 2]
• 8 vs 1 → swap → [3, 5, 1, 8, 2]
• 8 vs 2 → swap → [3, 5, 1, 2, 8]
→ 8 is now locked in its final position ✓
Pass 2 — Repeat, excluding the last element → 5 locks in place
Pass 3 → 3 locks Pass 4 → 2 locks
Result: [1, 2, 3, 5, 8] ✅
The key metric is the number of comparisons. With n elements, each pass compares (n−1), (n−2), …, 1 pairs. The total is n(n−1)/2, which simplifies to O(n²).
| Case | Condition | Complexity |
|---|---|---|
| Best | Already sorted | O(n) |
| Average | Random order | O(n²) |
| Worst | Reverse sorted | O(n²) |
The Best case O(n) is achieved with the swapped flag optimization. If a full pass completes with zero swaps, the array is already sorted — we can stop immediately. That's exactly what if (swapped == 0) break; does in the C code above.
Swapping only requires a single temp variable, so no extra array or data structure is needed. This makes it an In-Place sorting algorithm with a space complexity of O(1).
Because it modifies the original array directly, make sure to copy the array first if you need to preserve the original data.
Bubble Sort is a Stable sorting algorithm. When two elements have the same value, their original relative order is preserved after sorting.
This works because swaps only happen under a strictly greater (>) condition. If you change the condition to >=, equal elements may get reordered and stability is broken.
| Algorithm | Average | Worst | Space | Stable? |
|---|---|---|---|---|
| Bubble Sort | O(n²) | O(n²) | O(1) | ✓ Yes |
| Selection Sort | O(n²) | O(n²) | O(1) | ✗ No |
| Insertion Sort | O(n²) | O(n²) | O(1) | ✓ Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n) | ✓ Yes |
| Quick Sort | O(n log n) | O(n²) | O(log n) | ✗ No |
Bubble Sort works well when the dataset is small (roughly 100 elements or fewer) or when the data is nearly sorted already. For large datasets (thousands of elements or more), prefer Quick Sort or Merge Sort with O(n log n) performance.
Interview tip: Don't just write the code — be ready to explain why it's O(n²), what the swapped optimization does, and why stability matters. That demonstrates deep understanding.